最长等差数列的个数

题目描述
给定一个整数数组 nums，返回该数组中所有长度至少为 3 的等差子序列的个数。
注意：等差子序列不需要连续，但原序列顺序需保持，且至少包含 3 个元素。若有多个不同位置的等差子序列满足条件，应分别计数。

示例
输入：nums = [2,4,6,8,10]
输出：7
解释：所有长度至少为 3 的等差子序列包括：
[2,4,6]、[2,4,6,8]、[2,4,6,8,10]、[2,6,10]、[4,6,8]、[4,6,8,10]、[6,8,10] 共 7 个。

解题过程循序渐进讲解

第一步：理解问题核心
本题与单纯求最长等差数列长度不同，它需要统计个数。
关键点：

1. 子序列是顺序保持的，但不要求连续。
2. 长度至少为 3。
3. 相同数字在不同位置视为不同序列（因为下标不同）。

难点：直接枚举所有子序列会超时，需用动态规划高效统计。

第二步：状态定义
设 dp[i][d] 表示以第 i 个元素结尾、公差为 d 的等差子序列的数量。
但公差 d 可能很大（例如数字范围大时），直接用数组会过大。
改进：用哈希表数组，dp[i] 是一个哈希表，键是公差 d，值是以 nums[i] 结尾、公差为 d 的等差子序列的个数。

但这样只记录以 i 结尾的序列数，还需要知道长度至少为 3 的序列数。
我们拆分：
定义 dp[i][j] 表示以 nums[i] 和 nums[j] 作为最后两个元素的等差子序列的数量（长度至少为 2）。
为什么这样定义？因为对于长度 ≥3 的序列，我们只需在其前面至少加一个元素即可。

更精确地，我们定义：
dp[j][d] 表示以 nums[j] 结尾、公差为 d 的等差子序列的数量（长度至少为 2），
其中 d = nums[j] - nums[i]，i 是 j 之前的某个下标。

但为了统计长度 ≥3 的序列，我们可以在构建过程中累加：
当找到一个 i 和 j 时，如果存在以 nums[i] 结尾、公差为 d 的序列（长度至少为 2），则这些序列后面加上 nums[j] 就形成了长度至少为 3 的序列，可以直接累加到答案中。

第三步：状态转移推导
遍历所有 j 从 0 到 n-1，对每个 j，遍历所有 i 从 0 到 j-1，计算公差 d = nums[j] - nums[i]。

设 count[i][d] 表示以 nums[i] 结尾、公差为 d 的等差子序列数量（长度至少为 2）。
当我们固定 i 和 j 时：

1. 以 nums[i] 和 nums[j] 作为最后两个元素的序列，可以由“以 nums[i] 结尾、公差为 d 的序列”后面加上 nums[j] 形成。
2. 这样的序列有多少个？就是 count[i][d]。
3. 这些序列的长度至少为 3，所以我们把 count[i][d] 加到最终答案中。
4. 然后，我们需要更新 count[j][d]，表示以 nums[j] 结尾、公差为 d 的序列数量增加了。增加了多少？增加了 count[i][d] + 1，其中 +1 表示只有 nums[i] 和 nums[j] 两个元素的序列。

初始化：所有的 count[i][d] 一开始为空（0）。

第四步：具体步骤

1. 初始化一个哈希表数组 dp，dp[i] 是一个字典，键是公差 d，值是以 nums[i] 结尾、公差为 d 的长度至少为 2 的等差子序列数量。
2. 初始化答案 ans = 0。
3. 遍历 j 从 0 到 n-1：
   • 遍历 i 从 0 到 j-1：
     • 计算 d = nums[j] - nums[i]。
     • 获取以 nums[i] 结尾、公差为 d 的序列数：cnt = dp[i].get(d, 0)。
     • 把 cnt 加到 ans 中（因为这些序列长度至少为 2，加上 nums[j] 后长度至少为 3）。
     • 更新 dp[j][d]：dp[j][d] = dp[j].get(d, 0) + cnt + 1。
       解释：cnt 是之前以 nums[i] 结尾的长度 ≥2 的序列，它们加上 nums[j] 后仍然以 nums[j] 结尾，长度 ≥3；+1 是新增的由 nums[i] 和 nums[j] 两个元素组成的序列（长度=2）。
4. 遍历结束后，ans 即为所求。

第五步：示例推演
以 nums = [2,4,6,8,10] 为例：
n=5，初始化 dp[0..4] 均为空字典。

• j=1 (nums[1]=4)：
  i=0: d=4-2=2，dp[0] 中 d=2 不存在，cnt=0，ans+=0，更新 dp[1][2]=0+1=1。

• j=2 (nums[2]=6)：
  i=0: d=4，cnt=0，ans+=0，dp[2][4]=1。
  i=1: d=2，cnt=dp[1][2]=1，ans+=1，dp[2][2]=0+1+1=2。
  此时 ans=1（对应序列[2,4,6]）。

• j=3 (nums[3]=8)：
  i=0: d=6，cnt=0，ans+=0，dp[3][6]=1。
  i=1: d=4，cnt=dp[1][4]? 不存在→0，ans+=0，dp[3][4]=1。
  i=2: d=2，cnt=dp[2][2]=2，ans+=2，dp[3][2]=0+2+1=3。
  此时 ans=1+2=3（新增 [2,4,6,8]、[4,6,8]）。

• j=4 (nums[4]=10)：
  i=0: d=8，cnt=0，ans+=0，dp[4][8]=1。
  i=1: d=6，cnt=0，ans+=0，dp[4][6]=1。
  i=2: d=4，cnt=dp[2][4]=1，ans+=1，dp[4][4]=0+1+1=2。
  i=3: d=2，cnt=dp[3][2]=3，ans+=3，dp[4][2]=0+3+1=4。
  此时 ans=3+1+3=7（新增 [2,4,6,8,10]、[2,6,10]、[4,6,8,10]、[6,8,10]）。

最终 ans=7，与示例一致。

第六步：复杂度分析

• 时间复杂度：O(n²)，因为两重循环遍历所有 (i,j) 对。
• 空间复杂度：O(n²)，最坏情况下每个 dp[i] 可能有 O(n) 个不同的公差。

第七步：代码实现要点
可以用字典列表实现 dp，注意使用长整型（Python 的 int 自动支持大数）。
代码框架：

def numberOfArithmeticSlices(nums):
    n = len(nums)
    dp = [{} for _ in range(n)]  # dp[i][d] = 以 nums[i] 结尾、公差为 d 的长度≥2 的等差序列数
    ans = 0
    for j in range(n):
        for i in range(j):
            d = nums[j] - nums[i]
            cnt = dp[i].get(d, 0)
            ans += cnt
            dp[j][d] = dp[j].get(d, 0) + cnt + 1
    return ans

总结
本题通过动态规划，以每个位置为结尾、记录不同公差的序列数量，并在构建过程中累加长度 ≥3 的序列数。关键是把“长度至少为 2”的序列数存储起来，用于扩展成长度至少为 3 的序列，并同时统计答案。