[数据结构与算法]力扣413-等差数列划分——动态规划

题目描述

如果一个数列 至少有三个元素 ，并且任意两个相邻元素之差相同，则称该数列为等差数列。

例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。
给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的子数组个数。

子数组 是数组中的一个连续序列。

解题思路

看这道题目的时候也是没有任何思路，甚至读错了题目：要求子数组是数组中连续的序列，所以(1,3,5)并不是(1,2,3,4,5)的子数组。建立一个数组 arr 用于存放以每个元素结尾的子数组，因为子数组必须满足三个元素，所以从数组的第三个（索引为2）的元素开始搜索。

假设数组为? ?(1,2,3,4,5,6,7)

• 3? --->? arr[ 2 ] = 1;? ?(1,2,3)
• 4? --->? arr[ 3 ] = 2;? ?(1,2,3,4);? (2,3,4)
• 5? --->? arr[ 4 ] = 3;? (1,2,3,4,5);? (2,3,4,5);? (3,4,5)
• 6? --->? arr[ 5 ] = 4;? (1,2,3,4,5,6);? (2,3,4,5,6);? (3,4,5,6);? (4,5,6)
• 7? --->? arr[ 6 ] = 5;? (1,2,3,4,5,6,7);? (2,3,4,5,6,7);? (3,4,5,6,7);? (4,5,6,7);? (5,6,7)

发现以每一个元素结尾找到的子数组的个数恰好比上一个元素结尾的子数组个数多一个，所以数组(1,2,3,4,5,6,7)的子数组个数就是将每个元素结尾的子数组个数找出来作求和。故这个数组的子数组个数为：1+2+3+4+5=15

所以状态转移方程就很明确了

arr [ i ] =?arr [ i -1 ] +1

然后将?arr?数组求和即可。

输入输出示例

?

代码

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int len = nums.length;
        int[] arr = new int[len];
        for(int i = 2; i < len; i++){
            if(nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]){
                arr[i] = arr[i - 1] + 1;
            }
        }
        int sum = 0;
        for(int cnt :arr){
            sum += cnt;
        }
        return sum;
    }
}