线性动态规划：最长等差数列（基础版——统计长度至少为3的不同等差数列的个数）

题目描述
给定一个整数数组 nums，返回该数组中所有长度 至少为 3 的 不同 等差数列的 个数。
一个等差数列由至少三个元素组成，并且任意两个相邻元素的差相等。
注意：

1. 等差数列必须是原数组中 连续的 子数组（子数组是连续的，不能跳跃选取）。
2. 等差数列是 不同 的：只要起始位置或结束位置不同，就视为不同的等差数列。
3. 数组长度在 [1, 1000] 之间，数组元素在 [0, 500] 之间。

示例
输入：nums = [2, 4, 6, 8, 10]
输出：7
解释：长度至少为3的等差数列有：

• [2, 4, 6]

• [4, 6, 8]

• [6, 8, 10]

• [2, 4, 6, 8]

• [4, 6, 8, 10]

• [2, 4, 6, 8, 10]

• [2, 4, 6, 8, 10] 实际上与上一条相同，但注意这里我们统计的是 所有连续子数组，所以上面每个都是独立的。让我们更精确地列出所有 连续的 长度 ≥ 3 的等差数列子数组：
  [2,4,6]、[4,6,8]、[6,8,10]、[2,4,6,8]、[4,6,8,10]、[2,4,6,8,10]、[2,4,6,8,10]？不对，最后两个其实都是整个数组，但同一个子数组只算一次。我们仔细算一下：
  从索引 0 到 2: [2,4,6]
  索引 1 到 3: [4,6,8]
  索引 2 到 4: [6,8,10]
  索引 0 到 3: [2,4,6,8]
  索引 1 到 4: [4,6,8,10]
  索引 0 到 4: [2,4,6,8,10]
  一共 6 个？等等，题目要求输出 7。我们漏了一个：
  索引 0 到 2: [2,4,6]
  索引 1 到 3: [4,6,8]
  索引 2 到 4: [6,8,10]
  索引 0 到 3: [2,4,6,8]
  索引 1 到 4: [4,6,8,10]
  索引 0 到 4: [2,4,6,8,10]
  这只有 6 个。但示例说输出 7，我们核对一下：
  实际上，对于整个数组 [2,4,6,8,10]，它内部还包含更长的等差数列子数组吗？比如 [2,4,6,8] 和 [4,6,8,10] 已经算过了。
  让我们重新理解：题目要求“长度至少为3的不同等差数列的个数”，这里的“不同”是指子数组的起始和结束索引不同就算不同。
  整个数组 [2,4,6,8,10] 本身是一个等差数列，长度为5。
  除了这个，还有哪些长度至少为3的连续子数组是等差数列？
  列出所有长度≥3的连续子数组：
  长度3: [2,4,6], [4,6,8], [6,8,10] → 3个
  长度4: [2,4,6,8], [4,6,8,10] → 2个
  长度5: [2,4,6,8,10] → 1个
  总共 3+2+1 = 6个。但示例输出是7，似乎矛盾。
  实际上，常见的 LeetCode 413. Arithmetic Slices 题目是计算 连续的等差子数组的个数，但要求是长度至少为3。它的示例 [1,2,3,4] 输出为 3，对应的等差子数组是：[1,2,3], [2,3,4], [1,2,3,4]。
  对于 [2,4,6,8,10]，按照同样逻辑：
  长度3: [2,4,6], [4,6,8], [6,8,10] → 3
  长度4: [2,4,6,8], [4,6,8,10] → 2
  长度5: [2,4,6,8,10] → 1
  总和 = 3+2+1 = 6？但 LeetCode 413 示例输出是 7？我查一下：实际上 LeetCode 413 示例 [1,2,3,4] 输出3，[1,2,3,4,5] 输出6，[2,4,6,8,10] 输出7？等等，我们仔细算一下 [1,2,3,4,5]：
  长度3: [1,2,3], [2,3,4], [3,4,5] → 3
  长度4: [1,2,3,4], [2,3,4,5] → 2
  长度5: [1,2,3,4,5] → 1
  总和 3+2+1=6，正确。
  对于 [2,4,6,8,10]，差值都是2，同样结构：3+2+1=6，但示例说输出7，可能我记错了。
  我们按照正确逻辑来：题目是 统计长度至少为3的不同等差数列的个数，等差数列是 连续的 子数组。
  我们定义等差子数组：如果连续三个数 nums[i], nums[i+1], nums[i+2] 是等差数列，那么它们构成一个长度为3的等差子数组。
  如果更长的连续子数组也是等差，那么它包含多个长度为3的等差子数组。
  例如 [1,2,3,4] 包含两个长度为3的等差子数组：[1,2,3] 和 [2,3,4]。
  实际上，LeetCode 413 的解法通常用动态规划，定义 dp[i] 为以 i 结尾的长度至少为3的等差子数组个数。
  但这里我们明确一下：本题要求的是所有长度至少为3的等差连续子数组的个数，而不是只统计长度为3的。
  我们直接给出正确示例：
  输入 nums = [1,2,3,4]，输出为 3。
  输入 nums = [1,2,3,4,5]，输出为 6。
  输入 nums = [2,4,6,8,10]，输出为 6？还是7？
  我们按照公式：对于一个长度为 L 的连续等差段，它包含的长度至少为3的等差子数组个数为 (L-2)*(L-1)/2。
  对于 [2,4,6,8,10]，L=5，(3*4)/2 = 6，所以输出应为 6。
  但为了与常见题目一致，我们这里按照 LeetCode 413 来定义：
  题目实际上是 LeetCode 413. Arithmetic Slices（等差数列划分），它计算的是 所有连续的、长度至少为3的等差子数组的个数。
  我们重新表述题目：
  给定整数数组 nums，返回数组 nums 中所有为等差数组的 连续子数组 个数。
  子数组是连续的。
  示例：nums = [1,2,3,4] → 输出 3
  nums = [1,2,3,4,5] → 输出 6
  解释：
  [1,2,3,4] 有 3 个等差子数组：[1,2,3], [2,3,4], [1,2,3,4]。
  注意：[1,2,3,4] 本身也是等差子数组（长度4），所以总共有 3 个。

  我们接下来基于这个定义来讲解。

解题过程循序渐进讲解

步骤1：理解问题与初步思考
我们需要找到所有连续的子数组，这些子数组长度 ≥ 3，且是等差数列。
等差数列意味着对于子数组任意相邻两个元素，差值相同。
暴力枚举所有子数组：枚举起点 i 和终点 j，检查是否等差，时间复杂度 O(n³)，n=1000 时太慢。
我们需要更高效的方法。

步骤2：寻找规律与动态规划状态定义
观察一个长的等差连续段，例如 [1,2,3,4,5]：

• 以 3 结尾的等差子数组：[1,2,3]
• 以 4 结尾的等差子数组：[2,3,4] 和 [1,2,3,4]
• 以 5 结尾的等差子数组：[3,4,5]、[2,3,4,5]、[1,2,3,4,5]
  我们发现，如果知道以某个位置结尾的等差子数组个数，就可以累加得到总数。

定义 dp[i]：表示以 nums[i] 结尾的、长度至少为 3 的等差连续子数组的个数。
注意：这个定义是 以 i 结尾，并且子数组必须包含 nums[i] 且长度 ≥ 3。

但直接这样定义不好转移，因为我们不知道前面是否等差。
更常见的定义是：
设 diff[i] = nums[i] - nums[i-1] 为相邻差值。
我们考虑连续三个数 nums[i-2], nums[i-1], nums[i]，如果它们等差，即 nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，那么这三个数构成一个长度为3的等差子数组。
如果前面已经有一个以 i-1 结尾的等差子数组，并且新加入的 nums[i] 保持相同的公差，那么可以扩展出新的更长的等差子数组。

步骤3：状态转移方程推导
定义 dp[i]：以 nums[i] 结尾的、长度 ≥ 3 的等差连续子数组的个数。
考虑 nums[i] 能否与前面形成新的等差子数组：

• 如果 nums[i] - nums[i-1] == nums[i-1] - nums[i-2]，说明 nums[i-2], nums[i-1], nums[i] 是一个等差三元组。
  那么，所有以 nums[i-1] 结尾的等差子数组（长度 ≥ 3），在末尾加上 nums[i] 后，仍然保持等差，并且长度增加1，这些子数组的数量就是 dp[i-1]。
  此外，还会新增一个长度为3的等差子数组 [nums[i-2], nums[i-1], nums[i]]。
  因此，dp[i] = dp[i-1] + 1。
• 如果不满足上述条件，则 dp[i] = 0，因为以 nums[i] 结尾的、长度 ≥ 3 的等差子数组不存在。

步骤4：边界条件与初始化

• 对于 i < 2，没有足够元素形成长度 ≥ 3 的子数组，所以 dp[0] = dp[1] = 0。
• 从 i = 2 开始计算。

步骤5：计算总数
我们需要的是整个数组中所有这样的子数组的个数，因此答案是所有 dp[i] 的总和（i 从 2 到 n-1）。

步骤6：示例演算
以 nums = [1,2,3,4,5] 为例：
初始化 dp[0]=0, dp[1]=0。
i=2: nums[2]=3, 差值 3-2=1, 2-1=1，相等 → dp[2] = dp[1] + 1 = 0 + 1 = 1。对应子数组 [1,2,3]。
i=3: nums[3]=4, 差值 4-3=1, 3-2=1，相等 → dp[3] = dp[2] + 1 = 1 + 1 = 2。对应新增子数组 [2,3,4] 和 [1,2,3,4]。
i=4: nums[4]=5, 差值 5-4=1, 4-3=1，相等 → dp[4] = dp[3] + 1 = 2 + 1 = 3。对应新增子数组 [3,4,5]、[2,3,4,5]、[1,2,3,4,5]。
总和 = dp[2]+dp[3]+dp[4] = 1+2+3 = 6，与预期一致。

步骤7：算法实现与复杂度
我们只需要遍历一次数组，维护当前的 dp 值，累加即可。
空间复杂度可以优化到 O(1)，因为我们只需要前一个 dp 值。

伪代码：

function numberOfArithmeticSlices(nums):
    n = len(nums)
    if n < 3:
        return 0
    total = 0
    dp = 0  // 表示以当前元素结尾的等差子数组个数
    for i from 2 to n-1:
        if nums[i] - nums[i-1] == nums[i-1] - nums[i-2]:
            dp = dp + 1
            total += dp
        else:
            dp = 0
    return total

步骤8：进一步理解
这个动态规划的本质是：当发现一个连续等差段时，每增加一个元素，就会新增若干个等差子数组（新增的数量恰好是当前连续等差段的长度减2）。
实际上，dp 变量可以理解为当前连续等差段的“扩展计数”。
例如，连续等差段长度为 L，则它包含的等差子数组总数为 (L-2)*(L-1)/2，这可以通过累加 dp 得到。

步骤9：验证复杂例子
nums = [1,3,5,7,9,15,20,25,30,35]

• 前5个是等差，L=5，贡献 6 个。
• 后4个 [15,20,25,30] 等差，L=4，贡献 3 个。
• 最后 [20,25,30,35] 等差，但注意 [15,20,25,30,35] 不是等差（因为 15 到 20 差 5，30 到 35 差 5，但中间 20 到 25 差 5，25 到 30 差 5，所以 [15,20,25,30,35] 实际等差？检查：15,20,25,30,35 每个差5，是等差。但我们的算法会处理为两个连续等差段：第一段 1,3,5,7,9；第二段 15,20,25,30,35？等一下，20,25,30,35 是连续的，15 与 20 差5，所以整个 15 到 35 是等差连续段？但数组是 [1,3,5,7,9,15,20,25,30,35]，15 前面是 9，差值为 6，所以等差中断。因此 15 开始新的一段。从 15 到 35 都是等差吗？15,20,25,30,35 每个差5，是连续的等差段，长度 L=5，贡献 6 个。所以总数为 6 + 6 = 12。
  用算法验证：
  初始化 dp=0, total=0
  i=2: 5-3=2, 3-1=2 → dp=1, total=1
  i=3: 7-5=2, 5-3=2 → dp=2, total=3
  i=4: 9-7=2, 7-5=2 → dp=3, total=6
  i=5: 15-9=6, 9-7=2 → 不相等，dp=0
  i=6: 20-15=5, 15-9=6 → 不相等，dp=0
  i=7: 25-20=5, 20-15=5 → 相等，dp=1, total=7
  i=8: 30-25=5, 25-20=5 → dp=2, total=9
  i=9: 35-30=5, 30-25=5 → dp=3, total=12
  正确。

总结
本题是经典的线性动态规划问题，通过定义 dp[i] 为以 i 结尾的长度 ≥ 3 的等差连续子数组个数，利用相邻差值的相等关系进行状态转移，最终累加得到答案。时间复杂度 O(n)，空间复杂度 O(1)。