最长等差子序列的个数

题目描述

给定一个整数数组 nums，返回数组中等差子序列的总数。

注意：

• 子序列是从数组中删除一些（或不删除）元素得到的序列，且不改变剩余元素的顺序。
• 等差子序列至少包含 3 个元素。
• 等差子序列中的元素可以不相邻，但必须保持原数组中的相对顺序。
• 等差子序列的公差可以是任意整数（包括负数或零）。

示例：

nums = [2,4,6,8,10]
输出：7
解释：所有等差子序列为：
[2,4,6]、[4,6,8]、[6,8,10]、
[2,4,6,8]、[4,6,8,10]、
[2,4,6,8,10]、
[2,6,10]。

解题思路

这是一个线性动态规划问题，但它需要记录多个状态。

1. 朴素想法

• 如果只求最长等差子序列的长度，可以定义 dp[i][d] 表示以 nums[i] 结尾、公差为 d 的最长等差子序列长度。
• 但本题要求个数，且序列长度至少为 3，因此需要考虑更细的状态设计。

2. 状态定义

设：

• dp[i][d]：以 nums[i] 结尾，公差为 d，长度 >= 2 的等差子序列的个数（这个长度>=2的定义是为了方便转移）。
• cnt[i][d]：以 nums[i] 结尾，公差为 d，长度 = 2 的等差子序列的个数。

为什么分这两个？

• 因为当长度 >= 3 时，可以从前一个状态 dp[j][d] 转移过来。
• 长度 = 2 时，可以直接从前面任意一个元素 nums[j] 与 nums[i] 组成一对，用于后续扩展为长度 >= 3。

注意：公差 d 可能非常大（因为数组元素值可能很大），不能直接用数组索引，而要用哈希表。

3. 转移方程

遍历 i 从 0 到 n-1，对于每个 j < i，计算公差：

d = nums[i] - nums[j]

对于 (i, d)：

1. 长度=2的等差子序列数量增加：

   cnt[i][d] += 1   # 新增一对 (nums[j], nums[i])
   

2. 长度>=3的等差子序列数量可以从 dp[j][d] 转移而来：

   dp[i][d] += dp[j][d] + cnt[j][d]
   

   解释：
   • dp[j][d] 表示以 nums[j] 结尾、长度>=3的序列后面追加 nums[i]，长度>=4。
   • cnt[j][d] 表示长度为2的序列（nums[k], nums[j]）后面追加 nums[i]，形成长度为3的序列。
     这两种情况都会形成以 nums[i] 结尾、公差为 d、长度>=3的等差子序列。

4. 结果累计

• 每当我们更新 dp[i][d] 时，就把 dp[i][d] 加到最终答案 ans 中，因为 dp[i][d] 统计的是长度 >=3 的序列个数。

5. 实现细节

• 使用字典（哈希表）存储每个索引 i 对应的公差映射。
• 时间复杂度：O(n²)，空间复杂度：O(n²) 最坏，但通常哈希表存储较少。

逐步演算（以 nums = [2,4,6,8,10] 为例）

初始化

ans = 0

i=0（nums[0]=2）

• 前面没有元素，直接跳过。

i=1（nums[1]=4）

• j=0：d=4-2=2
  • cnt[1][2] = 1 （新增一对(2,4)）
  • dp[1][2] += dp[0][2] + cnt[0][2] = 0 + 0 = 0
  • ans += 0
• 当前状态：
  • cnt[1]：{2:1}
  • dp[1]：{}

i=2（nums[2]=6）

• j=0：d=6-2=4
  • cnt[2][4] = 1 （新增(2,6)）
  • dp[2][4] += 0 + 0 = 0
• j=1：d=6-4=2
  • cnt[2][2] = 1 （新增(4,6)）
  • dp[2][2] += dp[1][2] + cnt[1][2] = 0 + 1 = 1
  • ans += 1 ✅（序列[2,4,6]）
• 当前状态：
  • cnt[2]：{4:1, 2:1}
  • dp[2]：{2:1}

i=3（nums[3]=8）

• j=0：d=6
  • cnt[3][6] = 1
  • dp[3][6] += 0 + 0 = 0
• j=1：d=4
  • cnt[3][4] = 1
  • dp[3][4] += dp[1][4] + cnt[1][4] = 0 + 0 = 0
• j=2：d=2
  • cnt[3][2] = 1 （新增(6,8)）
  • dp[3][2] += dp[2][2] + cnt[2][2] = 1 + 1 = 2
  • ans += 2 ✅（序列[4,6,8] 和 [2,4,6,8]）
• 当前状态：
  • cnt[3]：{6:1, 4:1, 2:1}
  • dp[3]：{2:2}

i=4（nums[4]=10）

• j=0：d=8
  • cnt[4][8] = 1
• j=1：d=6
  • cnt[4][6] = 1
• j=2：d=4
  • cnt[4][4] = 1
• j=3：d=2
  • cnt[4][2] = 1 （新增(8,10)）
  • dp[4][2] += dp[3][2] + cnt[3][2] = 2 + 1 = 3
  • ans += 3 ✅（序列[6,8,10]、[4,6,8,10]、[2,4,6,8,10]）
• 还有 j=2 时 d=4 吗？已经算过，但注意 j=2 时 d=4 之前 cnt[2][4]=1，现在：
  • j=2：d=4 已经在前面更新了 cnt[4][4]=1，但 dp[4][4] 呢？
  • dp[4][4] += dp[2][4] + cnt[2][4] = 0 + 1 = 1
  • ans += 1 ✅（序列[2,6,10]）
• j=1 时 d=6：dp[4][6] += dp[1][6] + cnt[1][6] = 0 + 0 = 0
• 最终 ans = 1 + 2 + 3 + 1 = 7 ✅

代码实现（Python）

def numberOfArithmeticSlices(nums):
    n = len(nums)
    dp = [{} for _ in range(n)]   # dp[i][d]：长度>=3的个数
    cnt = [{} for _ in range(n)]  # cnt[i][d]：长度=2的个数
    ans = 0
    
    for i in range(n):
        for j in range(i):
            d = nums[i] - nums[j]
            # 更新 cnt[i][d]
            cnt[i][d] = cnt[i].get(d, 0) + 1
            
            # 从 j 转移到 i
            if d in dp[j]:
                dp[i][d] = dp[i].get(d, 0) + dp[j][d]
                ans += dp[j][d]
            if d in cnt[j]:
                dp[i][d] = dp[i].get(d, 0) + cnt[j][d]
                ans += cnt[j][d]
    
    return ans

复杂度分析

• 时间复杂度：O(n²)，两重循环。
• 空间复杂度：O(n²)，最坏情况下每个 i 对每个 j 产生不同的公差。

关键点总结

1. 区分长度为 2 和长度 >=3 的状态，方便转移。
2. 用哈希表存储公差映射，避免数组过大。
3. 每次更新 dp[i][d] 时直接累加到答案，因为 dp[i][d] 记录的是以 i 结尾、长度>=3的序列数。

这样，我们就能高效地统计所有长度至少为 3 的等差子序列的个数。