最长等差子序列的个数 题目描述 给定一个整数数组 nums ，返回数组中所有为等差数列的子序列（注意：子序列不要求连续）的个数。如果一个序列中至少有三个元素，并且任意两个相邻元素之差相同，则称该序列为等差数列。 例如，给定 nums = [2,4,6,8,10] ，返回 7，因为该数组中有 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,6,10 ]。 注意：结果可能很大，你需要对结果取模 10^9+7。 解题过程循序渐进讲解 第一步：理解问题本质 题目要求统计所有长度至少为 3 的等差子序列的个数。注意是 子序列 ，不要求连续，且元素的顺序必须保持原数组中的顺序。 我们需要考虑所有可能的差值（公差），并对每个位置，考虑它作为等差数列末尾时的情况。 第二步：初步思考状态定义 一个直观的想法是定义 dp[i][d] 表示以索引 i 结尾，公差为 d 的等差子序列的个数。但公差可能取值范围很大（例如数值范围大），因此不能直接用数组索引表示公差。 我们可以用哈希表来存储公差。更具体地，我们定义： dp[i] 是一个哈希表，键是公差 diff ，值是以 nums[i] 结尾、公差为 diff 的等差子序列的个数（这里子序列长度至少为 2）。 但题目要求长度至少为 3，所以我们需要区分长度至少为 2 的序列和长度至少为 3 的序列。 第三步：更精细的状态定义 我们定义两个状态： dp_weak[i][diff] ：以 nums[i] 结尾，公差为 diff 的等差子序列的个数，且该子序列长度至少为 2。 dp_strong[i][diff] ：以 nums[i] 结尾，公差为 diff 的等差子序列的个数，且该子序列长度至少为 3。 最终答案就是所有 dp_strong[i][diff] 的总和。 第四步：状态转移推导 假设我们当前在位置 i ，我们查看之前的所有位置 j （ 0 <= j < i ）。 令 diff = nums[i] - nums[j] 。 我们考虑如何形成以 i 结尾、公差为 diff 的等差子序列： 对于 dp_weak[i][diff] ： 我们可以直接由 {nums[j], nums[i]} 形成一个长度为 2 的序列，所以它至少贡献 1。 此外，如果以 j 结尾、公差为 diff 的序列（长度至少为 2）已经存在，那么我们可以在这些序列后面追加 nums[i] ，从而得到更长的序列。注意，这些序列的长度至少为 2，追加后长度至少为 3，所以这些追加后的序列应该计入 dp_strong 而不是 dp_weak 。 因此， dp_weak[i][diff] 的增量来自于：从 j 开始的新长度为 2 的序列，即每次遇到一个 j ，就为 dp_weak[i][diff] 增加 1。 所以： dp_weak[i][diff] += 1 （对于每个 j ）。 对于 dp_strong[i][diff] ： 当我们看到 j 时，如果以 j 结尾、公差为 diff 的弱序列（长度至少为 2）已经存在，那么在这些弱序列后面追加 nums[i] 就会形成一个长度至少为 3 的强序列。 因此， dp_strong[i][diff] 的增量等于 dp_weak[j][diff] 。 同时，如果以 j 结尾、公差为 diff 的强序列已经存在，那么在这些强序列后面追加 nums[i] 也会形成新的强序列，所以 dp_strong[i][diff] 还应加上 dp_strong[j][diff] 。 所以： dp_strong[i][diff] += dp_weak[j][diff] + dp_strong[j][diff] 。 注意： dp_weak[j][diff] 和 dp_strong[j][diff] 是在处理到 i 时已经计算好的（因为 j < i ）。 第五步：优化实现 由于公差可能是负数，且数值范围可能很大，我们使用哈希表数组来表示 dp_weak 和 dp_strong 。具体地： dp_weak[i] 是一个字典，键是公差（整数），值是对应序列个数（取模后）。 dp_strong[i] 类似。 初始化：所有 dp_weak[i] 和 dp_strong[i] 为空字典。 最终答案：对所有 i 和所有 diff 的 dp_strong[i][diff] 求和。 算法步骤： 初始化 total_count = 0 。 遍历 i 从 0 到 n-1： 对于每个 j 从 0 到 i-1： 计算 diff = nums[i] - nums[j] 。 从 dp_weak[j] 中获取以 j 结尾、公差为 diff 的弱序列个数 weak_j （如果没有，则为 0）。 从 dp_strong[j] 中获取以 j 结尾、公差为 diff 的强序列个数 strong_j （如果没有，则为 0）。 更新 dp_strong[i][diff] += weak_j + strong_j 。 更新 dp_weak[i][diff] += 1 。 将 dp_strong[i] 中所有值累加到 total_count 中（注意取模）。 返回 total_count 。 第六步：示例推演 以 nums = [2,4,6,8,10] 为例： 初始化： i=0: 无操作。 i=1 (nums[ 1 ]=4): j=0, diff=2: weak_ j=0, strong_ j=0 dp_ strong[ 1][ 2 ] += 0 dp_ weak[ 1][ 2 ] += 1 → 变为 1 total_ count += dp_ strong[ 1][ 2 ] = 0 i=2 (nums[ 2 ]=6): j=0, diff=4: dp_ weak[ 0][ 4] 不存在 → weak_ j=0, strong_ j=0 dp_ strong[ 2][ 4 ] += 0 dp_ weak[ 2][ 4 ] += 1 j=1, diff=2: weak_ j = dp_ weak[ 1][ 2] = 1, strong_ j=0 dp_ strong[ 2][ 2 ] += 1+0 = 1 dp_ weak[ 2][ 2 ] += 1 → 变为 1 total_ count += dp_ strong[ 2][ 2] = 1 (对应序列 [ 2,4,6 ]) i=3 (nums[ 3 ]=8): j=0, diff=6: dp_ weak[ 3][ 6 ] += 1 j=1, diff=4: weak_ j=dp_ weak[ 1][ 4]=0 → dp_ strong[ 3][ 4] += 0, dp_ weak[ 3][ 4 ] += 1 j=2, diff=2: weak_ j=dp_ weak[ 2][ 2]=1, strong_ j=dp_ strong[ 2][ 2 ]=1 dp_ strong[ 3][ 2 ] += 1+1 = 2 dp_ weak[ 3][ 2 ] += 1 total_ count 现在增加 dp_ strong[ 3][ 2]=2（对应 [ 4,6,8] 和 [ 2,4,6,8 ]） i=4 (nums[ 4 ]=10): j=0, diff=8: dp_ weak[ 4][ 8 ] +=1 j=1, diff=6: weak_ j=dp_ weak[ 1][ 6]=0 → dp_ strong[ 4][ 6] +=0, dp_ weak[ 4][ 6 ]+=1 j=2, diff=4: weak_ j=dp_ weak[ 2][ 4]=1, strong_ j=0 dp_ strong[ 4][ 4] +=1, dp_ weak[ 4][ 4 ]+=1 j=3, diff=2: weak_ j=dp_ weak[ 3][ 2]=1, strong_ j=dp_ strong[ 3][ 2 ]=2 dp_ strong[ 4][ 2 ] += 1+2 = 3 dp_ weak[ 4][ 2 ] +=1 total_ count 增加 dp_ strong[ 4][ 2]=3（对应 [ 6,8,10], [ 4,6,8,10], [ 2,4,6,8,10 ]） 另外，在 j=2, diff=4 时，dp_ strong[ 4][ 4] 增加了 1（对应 [ 2,6,10 ]）。 所以 total_ count 最终 = 1+2+3+1 = 7。 第七步：复杂度与总结 时间复杂度：O(n²)，因为我们需要两层循环遍历所有 (j, i) 对。 空间复杂度：O(n²) 最坏情况，因为每个位置可能存储 O(n) 个不同的公差（实际上因为 diff 是整数对差值，最坏可能有 O(n²) 个不同的键值对）。 关键点：用两个状态分别记录长度至少为 2 和长度至少为 3 的序列，通过累加之前的状态来计数。 通过以上步骤，我们就能正确统计所有长度至少为 3 的等差子序列的个数。