最长等差数列的个数（进阶版——统计长度至少为3的所有等差数列的个数） 题目描述 给定一个整数数组 nums ，返回数组中等差子序列的个数。等差子序列定义为：至少包含3个元素，且任意相邻两个元素之间的差值相等的子序列。子序列不必连续，但必须保持原数组中的相对顺序。 例如： 输入：nums = [ 2,4,6,8,10 ] 输出：7 解释：所有等差子序列为：[ 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 ]。 注意：子序列 [ 2,6,8 ] 不是等差数列，因为差值不恒定。 题目分析 这是一个“序列型”动态规划问题，需要统计所有长度至少为3的等差数列个数。难点在于： 子序列不要求连续，因此我们需要考虑所有可能的元素对作为等差序列的前两个元素。 等差数列的长度至少为3，因此统计时需要记录长度信息。 同一个等差子序列可能以不同的方式被构造出来，需要避免重复计数或遗漏。 一种自然的思路是：定义 dp[i][d] 表示以第 i 个元素结尾、公差为 d 的等差子序列的个数。但公差可能是负数，且值域可能很大，因此通常用哈希表数组来记录。更常用的定义是： dp[i][j] 表示以 nums[i] 和 nums[j] 作为最后两个元素的等差子序列的个数（其中 i < j ）。这样，当我们固定了最后两个元素，公差 d = nums[j] - nums[i] 也就确定了。 我们需要寻找在 i 之前的某个位置 k ，使得 nums[k] + d = nums[i] ，这样就可以将 k, i, j 组成一个长度为3的等差数列，并且可以将以 k, i 结尾的等差子序列后面接上 j ，形成更长的等差子序列。 具体解题步骤 步骤1：状态定义 设 dp[i][j] 表示以 nums[i] 和 nums[j] 作为最后两个元素的等差子序列的个数（其中 i < j ）。注意，这个子序列的长度至少为2。 最终答案是所有 dp[i][j] 的和，因为每个 dp[i][j] 对应了一组以 i, j 结尾的、长度至少为3的等差子序列（长度为2的序列不算答案，但 dp[i][j] 在递推时会被用于构建长度≥3的序列）。 步骤2：递推关系 对于每一对 (i, j) ，计算公差 d = nums[j] - nums[i] 。 我们需要找到在 i 之前的位置 k （ 0 ≤ k < i ），使得 nums[k] + d = nums[i] ，即 nums[k] = nums[i] - d 。 如果存在这样的 k ，那么所有以 k, i 结尾的等差子序列后面接上 j ，都会形成新的、以 i, j 结尾的等差子序列。 因此递推式为： \[ dp[ i][ j] = \sum_ {k: 0 \le k < i,\; nums[ k] = nums[ i] - d} (dp[ k][ i ] + 1) \] 这里的 +1 表示长度为3的新等差序列 (k, i, j) 。 注意： dp[k][i] 可能为0，此时 dp[k][i] + 1 就只表示长度为3的序列。 步骤3：初始化和计算顺序 初始化所有 dp[i][j] = 0 。 我们按 j 从 0 到 n-1 循环，对于每个 j ，内层循环 i 从 0 到 j-1，计算 dp[i][j] 。 在计算时，我们需要快速找到所有满足 nums[k] = nums[i] - d 的 k 。为了高效查找，可以在遍历过程中维护一个哈希表，记录每个数值最近出现的位置（但注意可能有重复值，所以需要记录所有出现位置）。更简便的方法是：在计算 dp[i][j] 时，我们遍历所有 k < i ，但这样总复杂度会达到 O(n^3)，在 n 较大时不可行。 优化：我们可以用哈希表 indexMap 记录每个数值对应的所有下标列表。对于给定的 i 和公差 d ，我们需要找到所有 k 满足 nums[k] = target = nums[i] - d 且 k < i 。我们可以从 indexMap[target] 中二分查找小于 i 的下标，然后累加对应的 dp[k][i] 。但这样仍然较慢。 更常见的优化是：定义 dp[i][j] 时，我们直接使用一个哈希表数组 dp[i] ，其中键是公差 d ，值是以 i 结尾、公差为 d 的等差子序列的个数（长度至少为2）。但这样我们需要同时记录长度至少为2的序列个数，并且要能快速累加。 步骤4：更高效的动态规划定义 定义 dp[i][d] 表示以 nums[i] 结尾、公差为 d 的等差子序列的个数（长度至少为2）。这里 d 是整数，可能很大，因此用哈希表实现。 转移时，对于每一对 (j, i) 其中 j < i ，计算 d = nums[i] - nums[j] ，则： \[ dp[ i][ d] \mathrel{+}= dp[ j][ d ] + 1 \] 这里的 +1 表示长度为2的序列 (j, i) 。 那么，长度为3及以上的等差子序列个数如何统计？ 注意，当我们在计算 dp[i][d] 时， dp[j][d] 表示以 j 结尾、公差为 d 的长度至少为2的序列个数。这些序列后面接上 i ，就形成了长度至少为3的序列。因此，在递推过程中，每次执行 dp[i][d] += dp[j][d] + 1 时， dp[j][d] 这部分就对应了长度至少为3的序列。 所以，我们可以在计算过程中累加所有 dp[j][d] 到答案中。 具体步骤： 初始化一个哈希表数组 dp ，长度为 n，每个元素是一个字典（映射公差到个数）。 初始化答案 ans = 0 。 遍历 i 从 0 到 n-1： 遍历 j 从 0 到 i-1： 计算 d = nums[i] - nums[j] 。 从 dp[j] 中获取以 j 结尾、公差为 d 的等差子序列个数 cnt = dp[j].get(d, 0) 。 将 cnt 加到答案 ans 中（因为 cnt 表示以 j 结尾、长度至少为2的等差序列，后面接上 i 就得到长度至少为3的序列）。 更新 dp[i][d] += cnt + 1 （ +1 表示新增长的度为2的序列 (j, i) ）。 返回 ans 。 步骤5：举例验证 以 nums = [2,4,6,8,10] 为例，演示过程： n=5，初始化 dp[0..4] 为空字典， ans=0 。 i=1, j=0: d=2 cnt = dp[ 0 ].get(2,0)=0 ans += 0 → ans=0 dp[ 1][ 2 ] = 0+1=1 i=2, j=0: d=4 cnt=0 → ans=0 dp[ 2][ 4 ]=1 j=1: d=2 cnt = dp[ 1 ].get(2,0)=1 ans += 1 → ans=1 （对应序列 [ 2,4,6 ]） dp[ 2][ 2 ] = 1+1=2 i=3, j=0: d=6 cnt=0 → ans=1 dp[ 3][ 6 ]=1 j=1: d=4 cnt = dp[ 1 ].get(4,0)=0 → ans=1 dp[ 3][ 4 ] = 0+1=1 j=2: d=2 cnt = dp[ 2 ].get(2,0)=2 ans += 2 → ans=3 （对应序列 [ 2,4,6,8] 和 [ 4,6,8 ]） dp[ 3][ 2 ] = 2+1=3 i=4, j=0: d=8 cnt=0 → ans=3 dp[ 4][ 8 ]=1 j=1: d=6 cnt=0 → ans=3 dp[ 4][ 6 ]=1 j=2: d=4 cnt = dp[ 2 ].get(4,0)=1 ans += 1 → ans=4 （对应序列 [ 2,6,8,10]？注意公差是4，但序列 [ 2,6,10] 公差是4吗？不对，这里 d=4 表示 nums[ j]=6, nums[ i]=10，所以是序列 [ 2,6,10]？但这里 cnt 来自 dp[ 2][ 4]=1，表示以索引2结尾、公差为4的序列个数。索引2是 nums[ 2]=6，公差为4的序列只有一个 [ 2,6]（长度为2），接上10得到 [ 2,6,10 ]。是的。） dp[ 4][ 4 ] = 1+1=2 j=3: d=2 cnt = dp[ 3 ].get(2,0)=3 ans += 3 → ans=7 （对应序列 [ 2,4,6,8,10]、[ 4,6,8,10]、[ 6,8,10 ]） dp[ 4][ 2 ] = 3+1=4 最终 ans=7，与示例一致。 步骤6：复杂度分析 时间复杂度：O(n^2)，因为需要枚举所有 (j, i) 对。内层哈希表操作是 O(1)。 空间复杂度：O(n^2)，最坏情况下每个 dp[i] 可能存储 O(n) 个不同的公差（例如所有数都相等时，公差0出现很多次）。 步骤7：边界情况 数组长度小于3时，直接返回0。 数组元素可能很大，公差可能超出32位整数范围，但题目一般保证在整数范围内。 数组可能有重复元素，我们的算法可以正确处理重复，因为 dp[j][d] 会累计所有以 j 结尾的序列。 总结 本题的核心是定义 dp[i][d] 表示以索引 i 结尾、公差为 d 的长度至少为2的等差子序列个数。在递推时，对于每一对 (j, i)，将 dp[j][d] 累加到答案中，同时更新 dp[i][d] 。这样就可以在一次 O(n^2) 的遍历中统计出所有长度至少为3的等差子序列个数。