最长等差数列（进阶版——允许公差为负且统计最长等差数列的个数）

题目描述

给定一个整数数组 nums，返回数组中最长等差数列的长度，并且统计所有最长等差数列的个数。等差数列允许公差为负数、零或正数，并且至少包含三个元素。如果多个等差数列长度相同且均为最长，你需要统计它们的个数。

例如：

• 输入：nums = [2,4,6,8,10]
  输出：最长长度 = 5，个数 = 1
  （因为只有一个等差数列 [2,4,6,8,10]）
• 输入：nums = [7,7,7,7]
  输出：最长长度 = 4，个数 = 1
  （公差为0的等差数列）
• 输入：nums = [0,2,2,3,4]
  输出：最长长度 = 3，个数 = 3
  （解释：最长长度为3的等差数列有三个：
  1. [0,2,4] 公差为2
  2. [2,2,2] 公差为0（索引0,2,4不行，这里必须是连续？不，子序列可以不连续，但必须保持原序，我们这里通常指“子序列”，但题目常为“子序列”，我们按“子序列”处理。但常见题是“最长等差数列子序列”，即可以不连续。但统计个数时，如果索引不同视为不同等差数列。但注意，如果值相同但索引位置不同，它们被视为不同的等差数列吗？通常题目要求统计不同的等差数列，是基于索引位置，而非值序列。但有时会规定“不同的等差数列”定义为值序列不同。我们需要明确。

本题我设定为：统计的是不同的等差数列子序列，即只要下标序列不同，即使值序列相同，也算不同的等差数列。例如 nums=[1,1,1]，公差为0，长度为3的等差数列有多个，因为你可以选不同下标的1。但实际上数组元素值可能重复，所以必须用下标来区分。但这样计数会非常大，可能不现实。因此，更常见的需求是：统计最长等差数列的个数，这里的“个数”指的是不同的等差数列子序列（即不同的下标选择）的个数。但这样会导致个数可能巨大，比如全等数组，长度为n，则长度≥3的等差数列子序列个数是组合数 C(n,3)+... 很多。所以通常题目不会这样统计。另一种合理的解释是：统计“最长等差数列的个数”，这里的“个数”指的是不同的公差值对应的最长等差数列的个数？这也不常见。

我们重新定义一下题目，以避免歧义：
题目：给定一个整数数组 nums，返回最长等差数列子序列的长度，并且统计所有长度为该最长长度的等差数列子序列的个数。注意，等差数列子序列是从原数组中选择一些元素（保持相对顺序）组成的序列，不要求连续。统计个数时，如果两个子序列的下标选择不同，则视为不同的等差数列，即使它们由相同的值组成。

由于数组长度可能达到 1000，元素范围在 0 到 10^9 之间，需要高效算法。

解题思路

这是一个经典的二维动态规划问题，类似于“最长等差数列子序列”，但需要同时记录长度和个数。

状态定义：
dp[i][d] 表示以索引 i 结尾，公差为 d 的等差数列子序列的最长长度，以及对应的方案数。但公差 d 可能很大（差值范围大），无法直接用数组索引。通常用哈希表来存储，即 dp[i] 是一个字典，键是公差 d，值是一个二元组 (len, cnt)，表示以 i 结尾公差为 d 的最长长度和方案数。

状态转移：
对于每个位置 i，我们遍历之前的所有位置 j (0 ≤ j < i)，计算差值 diff = nums[i] - nums[j]。那么，以 i 结尾公差为 diff 的等差数列可以由以 j 结尾公差为 diff 的等差数列接上 nums[i] 得到。设从 j 转移过来的长度为 dp[j][diff].len + 1，但我们需要考虑 j 是否已经存在以 diff 为公差的等差数列。

具体地：

1. 如果 dp[j] 中有键 diff，则表示存在以 j 结尾公差为 diff 的等差数列，其长度为 len_j，方案数为 cnt_j。那么，我们可以将 nums[i] 接在后面，形成长度 len_j + 1 的等差数列，方案数继承 cnt_j。
2. 如果 dp[j] 中没有键 diff，那么以 j 和 i 作为等差数列的前两项，形成一个长度为 2 的等差数列。但题目要求至少长度为 3，所以我们暂时不将其视为有效的等差数列（但需要记录长度为 2 的状态，以便后续扩展）。

为了统一，我们可以这样处理：

• 用 dp[i][diff] 存储以 i 结尾、公差为 diff 的等差数列的最长长度和方案数，但只记录长度 ≥ 2 的状态。
• 对于每对 (j, i)，差值 diff = nums[i] - nums[j]，我们看 j 是否有以 diff 结尾的等差数列：
  • 如果有，设其长度为 L，方案数为 C，则新长度 = L + 1，新方案数 = C。
  • 如果没有，则新长度 = 2，新方案数 = 1（即只有 nums[j] 和 nums[i] 两项）。
• 然后用新长度和方案数去更新 dp[i][diff]。注意，可能存在多个 j 给出相同的 diff，我们需要合并：如果新长度大于当前记录的长度，则替换为新的长度和方案数；如果新长度等于当前记录的长度，则方案数相加。

但这样存在一个问题：长度为 2 的状态我们不应该计入最终答案（因为题目要求至少长度为 3）。所以，我们在统计最终结果时，只考虑长度 ≥ 3 的等差数列。而且，我们需要统计的是全局最长的长度及其对应的方案总数。

为了不重复计数，我们需要谨慎地累加方案数。考虑一个例子：数组 [1,2,3,4]，公差 1 的等差数列：

• 以 3 结尾（索引 2）：可以从 (1,2) 得到长度 3，方案数 1；也可以从 (2,3) 得到长度 2（不计入结果）。
• 以 4 结尾（索引 3）：可以从 (1,2,3) 得到长度 4，方案数 1（延续了以 3 结尾的方案）；也可以从 (2,3) 得到长度 3，方案数 1；也可以从 (1,3) 得到长度 2（忽略）。
  这里，以 4 结尾长度 4 的方案数只有 1（来自 1,2,3,4），但长度 3 的方案数有多个（比如 2,3,4）。我们最终要的是全局最长的长度（这里是 4）对应的方案总数（这里是 1）。

所以，我们需要在动态规划过程中，记录全局最大长度 max_len 和全局方案总数 total_count。但注意，同一个等差数列可能会在不同的 i 位置被统计多次吗？不会，因为每个等差数列由其最后一个元素位置和公差唯一确定。但全局方案总数应该是所有以某个位置结尾、长度为 max_len 的等差数列的方案数之和。

算法步骤：

1. 初始化：

   • 令 n = len(nums)
   • 创建一个列表 dp，长度为 n，每个元素是一个字典（或哈希表），键为公差 diff，值为一个元组 (length, count)，表示以当前位置 i 结尾、公差为 diff 的等差数列的最长长度和方案数。
   • 初始化全局最长长度 max_len = 0，全局方案总数 total = 0。

2. 遍历 i 从 0 到 n-1：
   遍历 j 从 0 到 i-1：

   • 计算 diff = nums[i] - nums[j]
   • 从 dp[j] 中获取以 j 结尾公差为 diff 的信息：
     • 如果存在，设 (len_j, cnt_j) = dp[j][diff]，则新长度 new_len = len_j + 1，新方案数 new_cnt = cnt_j
     • 如果不存在，则新长度 new_len = 2，新方案数 new_cnt = 1（长度为 2 的等差数列）
   • 更新 dp[i][diff]：
     • 如果 diff 不在 dp[i] 中，则直接存入 (new_len, new_cnt)
     • 否则，设当前记录为 (cur_len, cur_cnt)：
       • 如果 new_len > cur_len，则替换为 (new_len, new_cnt)
       • 如果 new_len == cur_len，则方案数累加：cur_cnt += new_cnt，更新为 (cur_len, cur_cnt)
   • 注意，虽然长度为 2 的状态我们不计入最终结果，但必须记录，因为它可以扩展为更长的等差数列。
   • 更新全局答案：
     • 如果 new_len > max_len 且 new_len >= 3：
       • 更新 max_len = new_len
       • 更新 total = new_cnt
     • 如果 new_len == max_len 且 new_len >= 3：
       • 累加：total += new_cnt

3. 最终，如果 max_len < 3，则返回长度为 0，个数为 0（或者按题目要求，可能返回 0,0）。否则返回 (max_len, total)。

注意：上面更新全局答案时，如果同一个等差数列在不同的 i 被多次统计，就会重复。但我们的 total 是累加每个 i 结尾的方案数，而同一个等差数列只会在其最后一个位置被统计一次，所以不会重复。但有一个特殊情况：当有多个不同的 j 都能得到以 i 结尾、公差 diff、长度相同的等差数列时，这些等差数列是不同的（因为下标序列不同），它们会被合并到 dp[i][diff] 的方案数中。在更新全局答案时，我们只累加 new_cnt 一次（在更新 dp[i][diff] 时已经合并），所以不会多算。

但上面的更新方式可能会在 new_len == max_len 时重复累加，因为同一个 dp[i][diff] 可能会被多个 j 更新多次。例如，对于同一个 i 和 diff，可能有多个 j 产生相同的新长度，在更新 dp[i][diff] 时我们会合并方案数，但更新全局答案的步骤在每个 (j,i) 对都会执行，导致重复累加。所以，我们需要避免重复：应该在 dp[i][diff] 确定最终值之后，再用它去更新全局答案。但我们可以改为：在完成对所有 j 的遍历后，再检查 dp[i] 中每个公差对应的长度和方案数，去更新全局答案。但这样我们需要额外存储所有 dp[i][diff] 的最终值，然后再统一处理。

简化做法：在遍历 (j,i) 时，我们只是更新 dp[i][diff] 的临时状态，但为了不重复更新全局答案，我们可以先用一个临时字典记录 dp[i] 的最终值，然后再统一处理。但这样会增加内存。另一种方法是：在内部循环中，我们只记录 dp[i][diff] 的当前最优值，然后在更新 dp[i][diff] 的同时，如果发生了长度增加（或相等长度但方案数增加），我们可以更新全局答案，但要避免在同一个 i 和 diff 上多次累加。

更清晰的做法：

• 我们不在内部循环中更新全局答案，而是在内层循环结束后，遍历 dp[i] 中的所有条目，用它们更新全局答案。但这样复杂度会增加，因为每个 i 需要遍历其字典的所有公差。不过字典大小最多 O(n^2)（最坏情况每个 diff 都不同），但实际由于公差数量有限，可以接受。

我们采用最后这种：在每处理完一个 i 之后，遍历 dp[i] 中的所有公差 diff 对应的 (length, count)，如果 length ≥ 3 且 length > max_len，则更新 max_len 和 total；如果 length == max_len，则 total += count。

这样，我们保证了每个等差数列只在其结尾位置 i 被统计一次。

示例演算

以 nums = [2,4,6,8,10] 为例：

• i=0: dp[0] 为空
• i=1: j=0, diff=2, dp[0] 中没有 diff=2，所以 dp[1][2] = (2,1)
• i=2: j=0, diff=4 -> dp[2][4]=(2,1)
  j=1, diff=2 -> dp[1] 中有 (2,1) 对于 diff=2，所以 new_len=3, new_cnt=1 -> dp[2][2]=(3,1)
  遍历 dp[2]: (4,2,1) 长度2忽略；(2,3,1) 长度3，max_len=3, total=1
• i=3: j=0, diff=6 -> (2,1)
  j=1, diff=4 -> (2,1)
  j=2, diff=2 -> dp[2] 中有 (2,3,1)，所以 new_len=4, new_cnt=1 -> dp[3][2]=(4,1)
  遍历 dp[3]: 只有 (2,4,1) 长度4>3，所以更新 max_len=4, total=1
• i=4: j=0, diff=8 -> (2,1)
  j=1, diff=6 -> (2,1)
  j=2, diff=4 -> (2,1)
  j=3, diff=2 -> dp[3] 中有 (2,4,1)，所以 new_len=5, new_cnt=1 -> dp[4][2]=(5,1)
  遍历 dp[4]: (2,5,1) 长度5>4，更新 max_len=5, total=1
  结果：max_len=5, total=1

再以 nums = [0,2,2,3,4] 为例（统计最长长度为3的等差数列个数）：

• i=0: {}
• i=1: j=0, diff=2 -> (2,1)
• i=2: j=0, diff=2 -> (2,1) （与 dp[2][2] 合并？先看 j=1）
  j=1, diff=0 -> dp[1] 中没有 diff=0，所以 (2,1)
  现在 dp[2] 有两个条目：diff=2: (2,1)，diff=0: (2,1)
  长度均为2，忽略。
• i=3: j=0, diff=3 -> (2,1)
  j=1, diff=1 -> (2,1)
  j=2, diff=1 -> dp[2] 中没有 diff=1，所以 (2,1)（但 dp[2] 有 diff=2 和 0，没有1）
  所以 dp[3] 有 diff=3:(2,1), diff=1:(2,1)
• i=4: j=0, diff=4 -> (2,1)
  j=1, diff=2 -> dp[1] 中有 diff=2: (2,1) -> new_len=3, new_cnt=1 -> dp[4][2]=(3,1)
  j=2, diff=2 -> dp[2] 中有 diff=2: (2,1) -> new_len=3, new_cnt=1，但 dp[4][2] 已存在，且长度相等，所以方案数累加 -> dp[4][2]=(3,2)
  j=3, diff=1 -> dp[3] 中有 diff=1: (2,1) -> new_len=3, new_cnt=1 -> dp[4][1]=(3,1)
  遍历 dp[4]: diff=2: (3,2), diff=1: (3,1), diff=4: (2,1忽略)
  全局 max_len 更新为3，total 累加 2+1=3
  结果：max_len=3, total=3
  这三个等差数列分别是：

1. 索引 (0,1,4): 值 [0,2,4] 公差2
2. 索引 (1,2,4): 值 [2,2,4] 公差0? 等等，公差是 2-2=0, 4-2=2，不是等差数列！这里出错了。
   检查：nums[1]=2, nums[2]=2, nums[4]=4，差值序列为 0, 2，不是等差。所以我们的算法有问题，因为我们允许等差数列不连续，但必须满足所有相邻差值相等。对于索引 (1,2,4)，差值序列是 (0,2)，不相等，所以不是等差数列。但我们的转移错误地认为它是等差数列，因为我们只考虑了相邻的差值 diff，但等差数列要求所有相邻差值相等。在我们的状态定义中，dp[i][diff] 表示以 i 结尾、公差为 diff 的等差数列，这意味着从某个起始位置到 i，每相邻两项的差值都是 diff。当我们从 j 转移到 i 时，我们要求 nums[i]-nums[j]=diff，并且 j 结尾的等差数列公差也是 diff，这样接上之后公差保持一致。所以对于 (1,2,4)，当我们用 j=2, i=4, diff=2 时，dp[2] 中是否有 diff=2 的等差数列？dp[2] 中有 diff=2 的条目，但它是长度为 2 的等差数列，由索引 (0,2) 组成？不对，我们看看 dp[2] 怎么来的：

• i=2 时，j=0, diff=2 -> dp[2][2]=(2,1) 表示等差数列 [0,2]（索引0,2）
• j=1, diff=0 -> dp[2][0]=(2,1) 表示 [2,2]（索引1,2）
  所以 dp[2][2] 对应的是等差数列 [0,2]（值0和2），公差2。那么从 j=2 到 i=4，nums[4]-nums[2]=4-2=2，公差匹配，所以可以接上，形成 [0,2,4]，这才是正确的。所以 (1,2,4) 并不是等差数列，我们的算法不会把它算进去，因为当我们用 j=2 时，用的是 dp[2][2] 对应的等差数列 [0,2]，而不是 [2,2]。但上面我们在 i=4, j=2 时，用了 dp[2][2] 得到 new_len=3, new_cnt=1，这对应的是等差数列 [0,2,4]。之后 j=1 时，dp[1][2] 对应 [0,1]? nums[0]=0, nums[1]=2，所以等差数列 [0,2] 公差2，接上 nums[4]=4 得到 [0,2,4]，这与 j=2 得到的等差数列是同一个吗？下标序列不同：j=1 给出下标 (0,1,4)，j=2 给出下标 (0,2,4)。它们是两个不同的等差数列（因为下标序列不同），但值序列相同 [0,2,4]。所以我们的统计是正确的，确实有两个不同的等差数列（下标不同）具有相同的值序列。第三个等差数列是哪个？是公差为1的：从 j=3 得到 dp[3][1] 对应 [2,3]（下标2,3），接上 nums[4]=4 得到 [2,3,4] 公差1，下标 (2,3,4)。所以总共三个：
  1. 下标 (0,1,4): [0,2,4] 公差2
  2. 下标 (0,2,4): [0,2,4] 公差2
  3. 下标 (2,3,4): [2,3,4] 公差1
     它们的长度都是3，所以 total=3。

时间复杂度与空间复杂度

• 时间复杂度：O(n^2)，因为需要两重循环遍历所有 (j,i) 对。
• 空间复杂度：O(n^2)，最坏情况下每个 dp[i] 可能存储 O(n) 个不同的公差（因为 diff 可能很多），但实际由于整数范围有限，可能小一些。可以用哈希表存储。

代码实现（Python示例）

def longest_arith_seq_length_and_count(nums):
    n = len(nums)
    if n < 3:
        return 0, 0
    # dp[i] 是一个字典，键为公差 diff，值为 (length, count)
    dp = [{} for _ in range(n)]
    max_len = 0
    total = 0
    for i in range(n):
        for j in range(i):
            diff = nums[i] - nums[j]
            # 从 j 获取信息
            length_j, count_j = dp[j].get(diff, (1, 1))  # 如果不存在，则长度为1（只有nums[j]），但我们要的是长度为2的起始，所以这里长度为1，方案数为1
            new_len = length_j + 1
            new_cnt = count_j
            # 更新 dp[i]
            if diff in dp[i]:
                cur_len, cur_cnt = dp[i][diff]
                if new_len > cur_len:
                    dp[i][diff] = (new_len, new_cnt)
                elif new_len == cur_len:
                    dp[i][diff] = (cur_len, cur_cnt + new_cnt)
            else:
                dp[i][diff] = (new_len, new_cnt)
        # 处理完所有 j 后，用 dp[i] 更新全局答案
        for length, count in dp[i].values():
            if length >= 3:
                if length > max_len:
                    max_len = length
                    total = count
                elif length == max_len:
                    total += count
    return max_len, total

测试

print(longest_arith_seq_length_and_count([2,4,6,8,10]))  # (5, 1)
print(longest_arith_seq_length_and_count([7,7,7,7]))     # (4, 1)
print(longest_arith_seq_length_and_count([0,2,2,3,4]))   # (3, 3)
print(longest_arith_seq_length_and_count([1,2,3,4]))     # (4, 1)  # 解释：等差数列 [1,2,3,4] 只有一种下标选择（连续），但也可以有非连续的吗？例如 [1,3,4] 不是等差，[1,2,4] 不是等差，所以只有1个。

总结

本题是“最长等差数列”问题的扩展，要求统计最长等差数列的个数。关键点在于动态规划状态的设计：以每个位置结尾、每个公差为键，记录最长长度和方案数。转移时考虑前一个位置，注意长度为2的等差数列作为中间状态。最后统计全局最长长度及其对应的方案总数。