---

0413. 等差数列划分

• 标签：数组、动态规划、滑动窗口
• 难度：中等

题目链接

• 0413. 等差数列划分 - 力扣

题目大意

描述：

给定一个整数数组 $nums$。

要求：

返回数组 $nums$ 中所有为等差数组的「子数组」个数。

说明：

• 如果一个数列「至少有三个元素」，并且任意两个相邻元素之差相同，则称该数列为等差数列。
  • 例如，$[1,3,5,7,9]$、$[7,7,7,7] $和 $[3,-1,-5,-9]$ 都是等差数列。
• 「子数组」是数组中的一个连续序列。
• $1 \le nums.length \le 5000$。
• $-10^{3} \le nums[i] \le 10^{3}$。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：动态规划

1. 我们需要统计所有长度至少为 $3$ 的等差子数组的个数。
2. 使用动态规划，定义 $dp[i]$ 表示以位置 $i$ 结尾的等差子数组的个数。
3. 对于每个位置 $i$，如果 $nums[i] - nums[i-1] = nums[i-1] - nums[i-2]$，说明当前位置可以延续前面的等差子数组。
4. 如果满足等差条件，则 $dp[i] = dp[i-1] + 1$，其中 $+1$ 表示新增的长度为 $3$ 的等差子数组 $[nums[i-2], nums[i-1], nums[i]]$。
5. 如果不满足等差条件，则 $dp[i] = 0$。
6. 最终答案是所有 $dp[i]$ 的总和。

思路 1：代码

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return 0
        
        # dp[i] 表示以位置 i 结尾的等差子数组的个数
        dp = [0] * n
        result = 0
        
        # 从位置 2 开始遍历（因为至少需要 3 个元素）
        for i in range(2, n):
            # 检查是否满足等差条件
            if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
                # 可以延续前面的等差子数组
                dp[i] = dp[i-1] + 1
                # 累加到结果中
                result += dp[i]
            else:
                # 不满足等差条件，重置为 0
                dp[i] = 0
        
        return result

思路 1：复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组的长度。只需要遍历一次数组。
• 空间复杂度：$O(n)$，其中 $n$ 是数组的长度。使用了长度为 $n$ 的 $dp$ 数组。