题解：「力扣」第 413 题：等差数列划分（中等）

今天和大家分享的是「力扣」第 413 题：等差数列划分。这道题可以使用「滑动窗口」，也可以使用「动态规划」。

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

• 例如，[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

理解题意：

• 关键字：至少有三个元素；
• 子数组 是数组中的一个连续序列，「连续」这两个字重要；
• 求个数，不用求具体的连续子数组是哪些。

思路分析：

• 暴力解法，可以枚举所有长度大于

的连续子数组，如果是等差数列，给计数器加

；

• 只问个数，不问具体的连续子数组是哪些，有可能使用「动态规划」；
• 「连续」有可能使用「滑动窗口」。

方法一：滑动窗口

基本想法：一次遍历找每个可以延伸到最长的等差数列。所有长度大于等于

的 连续的 等差数列，一定来自输入数组里能够找到的若干个最长的 连续的 等差数列。

根据当前最长的连续等差数列的长度可以计算出长度大于等于

的连续等差数列的长度（简单推导一下就可以得到规律，后面讲）。因此可以使用「滑动窗口」找到当前输入数组上的 最长的 连续等差数列的长度

，计算

对结果的贡献。以数组 [2, 4, 6, 8, 12, 16, 20] 为例。

已经知道 [2, 4, 6, 8] 是首项为

，公差为

的等差数列时，加入 12 ，发现[2, 4, 6, 8, 12] 不是等差数列，因此左端点是 2，右端点更靠右的所有连续子数组都不会是（以 2 开头）的等差数列，并且以 4、6 为起点连续子区间也不用看了，从 8 开始继续找（8 有可能是下一段等差数列的开头，本例就特别地选择了这种特殊情况）。这是「滑动窗口」可以使用的原因：它是暴力解法的优化，少考虑了很多不用考虑的情况。

长度为

的等差数列对结果的贡献，可以举几个例子找规律，例如长度为

的等差数列对结果的贡献：

• 长度为

的连续的等差数列，有

个，如下图绿色线段；

• 长度为

的连续的等差数列，有

个，如下图黄色线段；

• 长度为

的连续的等差数列，有

个，如下图红色线段；

• 长度为

的连续的等差数列，有

个，如下图蓝色线段。

因此，长度为

的等差数列对结果的贡献为：

虽然上式需要在

的情况下才成立，但上式在

以及

的时候等于

，因此

的判断可以省去。

说明：以下「滑动窗口」的代码实际上没有写成一般的「滑动窗口」的样子，只需要从第 2 个元素开始，比较当前看到的元素和上一个元素的差，看一看「差」是否发生变化，就可以知道输入数组上等差数列的长度。

参考代码 1：

public class Solution {

    public int numberOfArithmeticSlices(int[] nums) {
        int len = nums.length;
        if (len < 3) {
            return 0;
        }
        // 初始化
        int preDiff = nums[1] - nums[0];
        // 当前得到的等差数列的长度，有「差」必有两个元素，因此初始化的时候 L = 2
        int L = 2;
        int res = 0;
        // 从下标 2 开始比较「当前的差」与「上一轮的差」是否相等
        for (int i = 2; i < len; i++) {
            int diff = nums[i] - nums[i - 1];
            if (diff == preDiff) {
                L++;
            } else {
                // 加入结果，然后重置 L 和 preDiff
                res += (L - 1) * (L - 2) / 2;
                L = 2;
                preDiff = diff;
            }
        }

        // 最后还要再计算一下结果
        res += (L - 1) * (L - 2) / 2;
        return res;
    }
}

复杂度分析：

• 时间复杂度：

，这里

是输入数组的长度；

• 空间复杂度：

。

方法二：动态规划

长度为 L 的等差数列，如果后面接上一个数，得到长度为 L + 1 的等差数列，那么它对结果的贡献可以从之前长度为 L 的等差数对结果的贡献得到。这一点表示了 不同子问题的结果之间的关系。因此可以使用「动态规划」。

状态定义：dp[i] 表示：以 nums[i] 结尾的、且长度大于等于

的连续子数组的个数。这个定义比较长，拆解一下：

• 必需以 nums[i] 结尾，nums[i] 必需被选取；
• 长度大于等于 3；
• 记录的是个数（不同于「方法一」的 L），就是题目要我们找的长度大于等于 3 的连续子数组（且是等差数列）的个数。

为什么是以 nums[i] 结尾呢？任何一个等差数列都会以某一个数结尾，再结合我们以前做过的「力扣」第 300 题（最长递增子序列），「力扣」第 53 题（最大子序和），连续子数组和子序列一般都定义成「以什么什么结尾」，不同规模的子问题的结果的联系比较容易找到。

状态转移方程：如果 nums[i] 能够接在 nums[i - 1] 之后形成一个长度更长的（在原数组上连续的）等差数列，那么 dp[i] = dp[i - 1] + 1 。这一点可以画个图找规律。

参考代码 2：

public class Solution {

    public int numberOfArithmeticSlices(int[] nums) {
        int len = nums.length;
        if (len < 3) {
            return 0;
        }
        
        // dp[i] 表示以：nums[i] 结尾的、且长度大于等于 3 的连续子数组的个数
        int[] dp = new int[len];
        int res = 0;
        // 从下标 2 开始，才有可能构成长度至少大于等于 3 的等差数列
        for (int i = 2; i < len; i++) {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
                dp[i] = dp[i - 1] + 1;
                res += dp[i];
            }
        }
        return res;
    }
}

说明：nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] 这么写隐含了判断等差数列的长度大于等于

。

复杂度分析：

• 时间复杂度：

，这里

是输入数组的长度；

• 空间复杂度：

。由于 dp[i] 只参考了 dp[i - 1]，可以使用「滚动变量」优化空间复杂度。

这就是今天的分享，感谢大家的收看。