最长等差数列的子序列（允许公差为零）

字数 3140 2025-12-16 19:28:32

最长等差数列的子序列（允许公差为零）

题目描述

给定一个整数数组 nums，返回数组中最长等差数列的子序列的长度。这里的“子序列”指的是从原数组中删除一些元素（也可以不删除）后，剩余元素保持原始顺序形成的序列。等差数列的公差可以是任意整数，包括零。例如，对于数组 [3, 6, 9, 12]，其最长等差数列子序列是它本身，长度为4，公差为3。对于数组 [1, 1, 1, 1]，最长等差数列子序列也是它本身，长度为4，公差为0。

注意，这道题要求的是“子序列”，而不是“子数组”。子序列的元素不必在原数组中连续，但顺序必须保持。这与之前讨论过的“最长连续递增子序列”或“最长等差数列子数组”不同。这是一个经典的线性动态规划问题，其状态设计较为巧妙。

解题过程

1. 问题分析与难点

本题的难点在于，等差数列由“公差”决定。如果我们知道了序列末尾的两个元素，就能确定公差。因此，一个直观的想法是：用动态规划的状态来记录以某个元素结尾、且具有特定公差的等差数列长度。

我们需要一种高效的方式来存储和查询“以某个元素结尾，公差为d的等差数列长度”。由于公差可能是任意整数，直接使用二维数组 dp[i][d] 会面临公差范围过大的问题（如果数组元素范围很大，公差可能从负很大到正很大）。为了优化，我们可以使用哈希表数组：dp[i] 是一个哈希表，键是公差 d，值是以 nums[i] 结尾、公差为 d 的等差数列的最长子序列长度。

2. 状态定义

设 dp[i] 是一个哈希表（或字典），dp[i][d] 表示以数组下标 i 的元素 nums[i] 结尾、且公差为 d 的等差数列的子序列的最大长度。

3. 状态转移方程

对于每一对下标 (j, i)，其中 0 <= j < i，我们可以计算出它们之间的公差：

\[d = nums[i] - nums[j] \]

现在考虑以 nums[i] 结尾、公差为 d 的等差数列。这样的等差数列可以由以 nums[j] 结尾、公差为 d 的等差数列后面加上 nums[i] 构成。因此，其长度等于以 nums[j] 结尾、公差为 d 的等差数列长度加1。

但这里有一个特殊情况：当 j 是等差数列中倒数第二个元素时，以 nums[j] 结尾、公差为 d 的等差数列长度至少为1（即只包含 nums[j] 一个元素）。所以，如果 dp[j] 中已经有键 d，那么：

\[dp[i][d] = dp[j][d] + 1 \]

如果 dp[j] 中没有键 d，说明之前没有以 nums[j] 结尾、公差为 d 的等差数列，那么由 nums[j] 和 nums[i] 可以组成一个新的等差数列，长度为2。因此：

\[dp[i][d] = 2 \]

在实现时，我们可以初始化所有 dp[i] 为空哈希表，然后对于每一对 (j, i)，计算公差 d，并更新 dp[i][d]。

4. 初始化与计算顺序

对于任意 i，dp[i] 初始化为空哈希表。
我们按顺序遍历 i 从 0 到 n-1，对于每个 i，再遍历 j 从 0 到 i-1。这样可以保证在计算 dp[i] 时，所有 j < i 的 dp[j] 都已经计算完毕。
在遍历过程中，我们需要记录全局最大值 ans，即所有 dp[i][d] 中的最大值。初始化 ans = 1，因为单个元素本身可以视为长度为1的等差数列（公差任意）。

5. 算法步骤（详细）

获取数组长度 n，如果 n <= 2，直接返回 n，因为任意两个（或一个）元素都构成等差数列。
初始化一个列表 dp，长度为 n，每个元素是一个空的字典（哈希表）。
初始化答案 ans = 2（因为 n >= 2，至少长度为2）。
外层循环 i 从 0 到 n-1：
- 内层循环 j 从 0 到 i-1：
  - 计算公差 diff = nums[i] - nums[j]。
  - 检查 dp[j] 中是否有键 diff：
    - 如果有，则 curr_len = dp[j][diff] + 1。
    - 如果没有，则 curr_len = 2。
  - 更新 dp[i][diff] 为 max(dp[i].get(diff, 0), curr_len)。
  - 更新全局答案 ans = max(ans, curr_len)。
返回 ans。

6. 示例演示

以 nums = [3, 6, 9, 12] 为例：

n=4，初始化 dp = [{}, {}, {}, {}], ans=2。
i=0: 内层循环不执行（j 从0到-1）。
i=1:
- j=0: diff = 6-3=3。dp[0] 为空，所以 curr_len=2。更新 dp[1][3]=2，ans=2。
i=2:
- j=0: diff=9-3=6。dp[0] 空，curr_len=2。更新 dp[2][6]=2。
- j=1: diff=9-6=3。dp[1] 中有键3，值为2，所以 curr_len=2+1=3。更新 dp[2][3]=3，ans=3。
i=3:
- j=0: diff=12-3=9，curr_len=2，dp[3][9]=2。
- j=1: diff=12-6=6，dp[1] 中没有键6（dp[1] 只有键3），所以 curr_len=2，dp[3][6]=2。
- j=2: diff=12-9=3，dp[2] 中有键3，值为3，所以 curr_len=3+1=4。更新 dp[3][3]=4，ans=4。

最终返回 ans=4，符合预期。

7. 复杂度分析

时间复杂度：O(n²)，因为有两层循环遍历所有数对 (j, i)。每次内层循环中，哈希表的操作（查询和插入）平均是O(1)的，所以总时间是O(n²)。
空间复杂度：O(n²)，最坏情况下，每个 dp[i] 可能存储O(i)个不同的公差，总共需要O(n²)的空间。但实际中，公差的种类数受限于数组元素的范围，如果元素范围有限，空间复杂度可能更低。

8. 边界情况与注意事项

数组长度小于等于2时，直接返回长度。
公差为零的情况被自然地包含在内。例如数组 [1,1,1]，当 i=2, j=1 时，diff=0，dp[1] 中可能已经有 {0:2}（来自 i=1, j=0），则 dp[2][0] = 2+1=3。
由于子序列可以不连续，所以我们需要遍历所有 j < i，而不只是 j = i-1。

9. 优化思路（可选）

本题的标准解法已经足够高效。如果数组长度非常大（例如n>1000），O(n²)的时间可能成为瓶颈，但这是目前已知最优的解法（基于动态规划）。在某些特定条件下（如数组元素范围很小），可以使用基于值域的DP进行优化，但通用性不强。

总结

本题通过定义状态 dp[i][d] 为以 nums[i] 结尾、公差为 d 的最长等差数列子序列长度，利用两层循环遍历所有数对，递推更新状态。最终答案是所有状态中的最大值。这个解法巧妙地处理了公差不定的问题，是解决最长等差数列子序列问题的经典动态规划方法。

最长等差数列的子序列（允许公差为零）题目描述给定一个整数数组 nums ，返回数组中最长等差数列的子序列的长度。这里的“子序列”指的是从原数组中删除一些元素（也可以不删除）后，剩余元素保持原始顺序形成的序列。等差数列的公差可以是任意整数，包括零。例如，对于数组 [3, 6, 9, 12] ，其最长等差数列子序列是它本身，长度为4，公差为3。对于数组 [1, 1, 1, 1] ，最长等差数列子序列也是它本身，长度为4，公差为0。注意，这道题要求的是“子序列”，而不是“子数组”。子序列的元素不必在原数组中连续，但顺序必须保持。这与之前讨论过的“最长连续递增子序列”或“最长等差数列子数组”不同。这是一个经典的线性动态规划问题，其状态设计较为巧妙。解题过程 1. 问题分析与难点本题的难点在于，等差数列由“公差”决定。如果我们知道了序列末尾的两个元素，就能确定公差。因此，一个直观的想法是：用动态规划的状态来记录以某个元素结尾、且具有特定公差的等差数列长度。我们需要一种高效的方式来存储和查询“以某个元素结尾，公差为d的等差数列长度”。由于公差可能是任意整数，直接使用二维数组 dp[i][d] 会面临公差范围过大的问题（如果数组元素范围很大，公差可能从负很大到正很大）。为了优化，我们可以使用哈希表数组： dp[i] 是一个哈希表，键是公差 d ，值是以 nums[i] 结尾、公差为 d 的等差数列的最长子序列长度。 2. 状态定义设 dp[i] 是一个哈希表（或字典）， dp[i][d] 表示以数组下标 i 的元素 nums[i] 结尾、且公差为 d 的等差数列的子序列的最大长度。 3. 状态转移方程对于每一对下标 (j, i) ，其中 0 <= j < i ，我们可以计算出它们之间的公差： \[ d = nums[ i] - nums[ j ] \] 现在考虑以 nums[i] 结尾、公差为 d 的等差数列。这样的等差数列可以由以 nums[j] 结尾、公差为 d 的等差数列后面加上 nums[i] 构成。因此，其长度等于以 nums[j] 结尾、公差为 d 的等差数列长度加1。但这里有一个特殊情况：当 j 是等差数列中倒数第二个元素时，以 nums[j] 结尾、公差为 d 的等差数列长度至少为1（即只包含 nums[j] 一个元素）。所以，如果 dp[j] 中已经有键 d ，那么： \[ dp[ i][ d] = dp[ j][ d ] + 1 \] 如果 dp[j] 中没有键 d ，说明之前没有以 nums[j] 结尾、公差为 d 的等差数列，那么由 nums[j] 和 nums[i] 可以组成一个新的等差数列，长度为2。因此： \[ dp[ i][ d ] = 2 \] 在实现时，我们可以初始化所有 dp[i] 为空哈希表，然后对于每一对 (j, i) ，计算公差 d ，并更新 dp[i][d] 。 4. 初始化与计算顺序对于任意 i ， dp[i] 初始化为空哈希表。我们按顺序遍历 i 从 0 到 n-1 ，对于每个 i ，再遍历 j 从 0 到 i-1 。这样可以保证在计算 dp[i] 时，所有 j < i 的 dp[j] 都已经计算完毕。在遍历过程中，我们需要记录全局最大值 ans ，即所有 dp[i][d] 中的最大值。初始化 ans = 1 ，因为单个元素本身可以视为长度为1的等差数列（公差任意）。 5. 算法步骤（详细）获取数组长度 n ，如果 n <= 2 ，直接返回 n ，因为任意两个（或一个）元素都构成等差数列。初始化一个列表 dp ，长度为 n ，每个元素是一个空的字典（哈希表）。初始化答案 ans = 2 （因为 n >= 2 ，至少长度为2）。外层循环 i 从 0 到 n-1 ：内层循环 j 从 0 到 i-1 ：计算公差 diff = nums[i] - nums[j] 。检查 dp[j] 中是否有键 diff ：如果有，则 curr_len = dp[j][diff] + 1 。如果没有，则 curr_len = 2 。更新 dp[i][diff] 为 max(dp[i].get(diff, 0), curr_len) 。更新全局答案 ans = max(ans, curr_len) 。返回 ans 。 6. 示例演示以 nums = [3, 6, 9, 12] 为例： n=4 ，初始化 dp = [{}, {}, {}, {}] , ans=2 。 i=0 : 内层循环不执行（ j 从0到-1）。 i=1 : j=0 : diff = 6-3=3 。 dp[0] 为空，所以 curr_len=2 。更新 dp[1][3]=2 ， ans=2 。 i=2 : j=0 : diff=9-3=6 。 dp[0] 空， curr_len=2 。更新 dp[2][6]=2 。 j=1 : diff=9-6=3 。 dp[1] 中有键3，值为2，所以 curr_len=2+1=3 。更新 dp[2][3]=3 ， ans=3 。 i=3 : j=0 : diff=12-3=9 ， curr_len=2 ， dp[3][9]=2 。 j=1 : diff=12-6=6 ， dp[1] 中没有键6（ dp[1] 只有键3），所以 curr_len=2 ， dp[3][6]=2 。 j=2 : diff=12-9=3 ， dp[2] 中有键3，值为3，所以 curr_len=3+1=4 。更新 dp[3][3]=4 ， ans=4 。最终返回 ans=4 ，符合预期。 7. 复杂度分析时间复杂度：O(n²)，因为有两层循环遍历所有数对 (j, i) 。每次内层循环中，哈希表的操作（查询和插入）平均是O(1)的，所以总时间是O(n²)。空间复杂度：O(n²)，最坏情况下，每个 dp[i] 可能存储O(i)个不同的公差，总共需要O(n²)的空间。但实际中，公差的种类数受限于数组元素的范围，如果元素范围有限，空间复杂度可能更低。 8. 边界情况与注意事项数组长度小于等于2时，直接返回长度。公差为零的情况被自然地包含在内。例如数组 [1,1,1] ，当 i=2, j=1 时， diff=0 ， dp[1] 中可能已经有 {0:2} （来自 i=1, j=0 ），则 dp[2][0] = 2+1=3 。由于子序列可以不连续，所以我们需要遍历所有 j < i ，而不只是 j = i-1 。 9. 优化思路（可选）本题的标准解法已经足够高效。如果数组长度非常大（例如n>1000），O(n²)的时间可能成为瓶颈，但这是目前已知最优的解法（基于动态规划）。在某些特定条件下（如数组元素范围很小），可以使用基于值域的DP进行优化，但通用性不强。总结本题通过定义状态 dp[i][d] 为以 nums[i] 结尾、公差为 d 的最长等差数列子序列长度，利用两层循环遍历所有数对，递推更新状态。最终答案是所有状态中的最大值。这个解法巧妙地处理了公差不定的问题，是解决最长等差数列子序列问题的经典动态规划方法。