【每日一题】413. 等差数列划分：动态规划，YYDS！

题目描述

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

例如，[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是等差数列。

给你一个整数数组 nums ，返回数组 nums 中所有为等差数组的 子数组 个数。

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

示例 1：

输入：nums = [1,2,3,4] 输出：3 解释：nums 中有三个子等差数组：[1, 2, 3]、[2, 3, 4] 和 [1,2,3,4] 自身。

示例 2：

输入：nums = [1] 输出：0

提示：

• 1 <= nums.length <= 5000
• -1000 <= nums[i] <= 1000

链接：https://leetcode-cn.com/problems/arithmetic-slices

动态规划

这道题使用动态规划来解是比较简单的，我们可以观察得到，以nums[i]为结尾的等差数列肯定可以在以nums[i-1]的基础上转换而来，比如，以[1,2,3,4]为例，4结尾的数量是3结尾的数量加1，分别为[1,2,3,4]为在原来[1,2,3]的基础上延续，同时新增了一种[2,3,4]，所以，动态规划定义如下：

状态定义：dp[i]表示以nums[i]为结尾的等差数列数量。

状态转移：如果nums[i]-nums[i-1]==nums[i-1]-nums[i-2]，dp[i]=dp[i-1]+1，否则dp[i]=0。

另外，dp转移方程只与前一项有关，所以，只需要一个变量即可。

请看代码：

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return 0;
        }

        int dp = 0, ans = 0;
        for (int i = 2; i < n; i++) {
            if (nums[i]-nums[i-1]==nums[i-1]-nums[i-2]) {
                ans += ++dp;
            } else {
                dp = 0;
            }
        }

        return ans;
    }
}

• 时间复杂度：O(n)，遍历一遍数组即可。
• 空间复杂度：O(1)，只需要几个临时变量。

运行结果如下：