最长等差数列的变种：统计长度至少为3的所有等差数列的个数

题目描述
给定一个整数数组 nums，请统计并返回该数组中所有长度至少为3的等差数列的个数。等差数列是指至少包含三个元素，并且任意两个相邻元素之间的差值相等的序列。在数组中，等差数列不需要连续，只要下标严格递增即可（即子序列）。例如，数组 [2,4,6,8,10] 中，子序列 [2,6,10] 是等差数列（差值为4），[2,4,6,8,10] 也是等差数列（差值为2）。注意，序列的元素顺序必须与原数组顺序一致。

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

• [2,4,6]（差值2）
• [2,4,6,8]（差值2）
• [2,4,6,8,10]（差值2）
• [2,6,10]（差值4）
• [4,6,8]（差值2）
• [4,6,8,10]（差值2）
• [6,8,10]（差值2）

解题思路
这是一个线性动态规划问题，我们需要统计所有长度至少为3的等差数列（子序列）的个数。
关键点在于如何高效地记录以每对元素结尾的等差数列信息，并递推计数。

步骤拆解

1. 状态定义
   定义 dp[i][d] 表示以索引 i 结尾，公差为 d 的等差子序列的个数。但公差可能很大，若直接用差值作为第二维，会因差值范围过大导致内存爆炸。
   改进：使用哈希表数组。
   令 dp[i] 是一个哈希表，键是公差 d，值是以 i 结尾、公差为 d 的等差子序列的个数（这些子序列的长度至少为2）。
   但我们需要长度至少为3的等差数列个数，所以还需另一个计数来累计答案。

2. 状态转移
   考虑当前下标 i 和之前的某个下标 j（0 ≤ j < i），差值 d = nums[i] - nums[j]。
   以 i 结尾、公差为 d 的等差子序列可以由两部分组成：

   • 从 j 接上 i 形成的长度为2的序列。
   • 从 j 接上 i，并且 j 之前已经存在以 j 结尾、公差为 d 的等差子序列（长度至少为2），这样就能形成长度至少为3的等差数列。

   具体转移：
   设 dp[j].get(d) 表示以 j 结尾、公差为 d 的等差子序列个数（这些子序列长度至少为2）。
   当考虑 (j, i) 时，公差 d = nums[i] - nums[j]：

   • 如果 dp[j] 中存在键 d，则说明在 j 之前已经有以 j 结尾、公差为 d 的长度至少为2的子序列。此时，将这些序列后面加上 nums[i]，就会形成长度至少为3的等差数列，个数为 dp[j][d]，这些要加到最终答案中。
   • 然后，以 i 结尾、公差为 d 的等差子序列个数需要增加：增加的数量是 dp[j][d] + 1。其中 +1 表示长度为2的新序列 [nums[j], nums[i]]，dp[j][d] 表示在 j 原来的序列基础上追加 nums[i] 形成的新序列（这些新序列长度至少为3，但这里只是用来递推更长序列，不计入答案，因为之前已经计入过了）。

   注意：为了避免重复计数，我们只在发现 dp[j][d] 存在时，将 dp[j][d] 加到答案中（这些序列是首次变成长度≥3的）。而 dp[i][d] 的更新是用于后续递推。

3. 初始化
   所有 dp[i] 初始为空哈希表。
   最终答案初始为0。

4. 遍历顺序
   外层循环 i 从 0 到 n-1，内层循环 j 从 0 到 i-1。
   对每对 (j, i) 计算公差 d，然后按上述转移。

5. 复杂度
   时间复杂度 O(n²)，空间复杂度 O(n²) 最坏（因为哈希表可能存很多公差）。

6. 示例推导
   以 nums = [2,4,6,8,10] 为例，展示部分过程：

   • i=0: dp[0]={}
   • i=1, j=0: d=2
     dp[0] 中没有键2，所以答案不增加。
     dp[1][2] += 1 （长度为2的序列[2,4]） → dp[1]={2:1}
   • i=2, j=0: d=4
     dp[0] 无键4 → dp[2][4] +=1 → dp[2]={4:1}
     j=1: d=2
     dp[1] 有键2，值=1 → 答案增加1（序列[2,4,6]）
     dp[2][2] += (dp[1][2] + 1) = 1+1=2 → dp[2]={4:1, 2:2}
     解释：dp[2][2]=2 表示以2结尾、公差2的等差子序列个数为2，即[4,6]和[2,4,6]（注意这里[2,4,6]长度≥3，但它是从j=1递推来的，只用于后续扩展，不计入新答案）

   后续类似，最终累计所有答案。

最终答案
遍历过程中累计的长度至少为3的等差数列总数即为所求。

代码框架（Python）

def numberOfArithmeticSlices(nums):
    n = len(nums)
    if n < 3:
        return 0
    
    dp = [{} for _ in range(n)]  # dp[i]是哈希表，键为公差，值为以i结尾、公差为该值的等差子序列个数（长度≥2）
    ans = 0
    
    for i in range(n):
        for j in range(i):
            d = nums[i] - nums[j]
            cnt = dp[j].get(d, 0)  # 以j结尾、公差d的长度≥2的序列个数
            ans += cnt  # 这些序列加上nums[i]就变成长度≥3的等差数列
            # 更新dp[i][d]，包括长度为2的新序列和从j扩展来的序列
            dp[i][d] = dp[i].get(d, 0) + cnt + 1
    
    return ans

验证示例
输入 [2,4,6,8,10]，代码运行后得到结果7，与示例一致。

思考
本题难点在于理解 dp[i][d] 存储的是长度至少为2的等差子序列个数，而答案只在从长度2扩展到长度3时累加。这样既避免了重复计数，又能覆盖所有长度≥3的等差数列。