LeetCode 1027. 最长等差数列
目录
题目描述
题意分析
给定一个整数数组，要在其中挑出若干个元素，保持它们在原数组中的先后次序，使得相邻两项之差恒定，问这样挑出来的序列最长能有多长。挑出来的元素不要求在原数组里连续，只要求下标递增。
「保持相对顺序」这一条决定了不能先排序再处理——排序会改变谁在谁前面，
[9, 4, 7, 2, 10]排完序变成[2, 4, 7, 9, 10]，里面的[2, 4]在原数组里是倒着的，不合法。约束里给出数组长度上限一千，元素取值在 0 到 500 之间。长度一千意味着平方级别的枚举是被允许的，甚至是被鼓励的；而取值范围有界，说明相邻两项之差落在 -500 到 500 之间，只有一千零一种可能。边界方面，数组至少有一个元素，此时答案是 1；公差允许为 0（
[3, 3, 3]是合法的等差序列），也允许为负（元素递减）。
解法：结尾位置 + 公差动态规划
核心思路
等差子序列是否能继续延长，只取决于「最后一个元素的位置」和「公差」，此前具体选过哪些下标不再重要。
定义
dp[i][d]：以nums[i]结尾、公差为d的最长等差子序列长度。枚举前驱j < i，令d = nums[i] - nums[j]：
dp[i][d] = max(dp[i][d], dp[j][d] + 1)若
dp[j][d]尚不存在，nums[j]与nums[i]本身就能组成长度为 2 的等差子序列，所以候选长度至少为 2。本题元素在
[0, 500]，公差只可能在[-500, 500]，将公差加 500 后可直接作为长度 1001 数组的下标。这样比哈希表更简单、常数也更小；若值域不受限，再改用每个结尾位置一张哈希表。
解题步骤
- 创建
dp[n][1001]，将全局答案初始化为 2；长度不足 2 时直接返回数组长度。- 依次枚举结尾位置
i，再枚举所有前驱j < i。- 计算偏移后的公差下标
diff = nums[i] - nums[j] + 500。- 候选长度为
max(2, dp[j][diff] + 1)，用它更新dp[i][diff]和全局答案。例如
[9, 4, 7, 2, 10]中，处理 10 时，前驱 7 对应公差 3；已有状态dp[7][3] = 2，接入 10 后得到长度 3 的[4, 7, 10]。
代码实现
class Solution {
public int longestArithSeqLength(int[] nums) {
int n = nums.length;
if (n <= 2) {
return n;
}
int[][] dp = new int[n][1001];
int ans = 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int diff = nums[i] - nums[j] + 500;
int length = Math.max(2, dp[j][diff] + 1);
dp[i][diff] = Math.max(dp[i][diff], length);
ans = Math.max(ans, dp[i][diff]);
}
}
return ans;
}
}
func longestArithSeqLength(nums []int) int {
if len(nums) <= 2 {
return len(nums)
}
dp := make([][1001]int, len(nums))
ans := 2
for i := range nums {
for j := 0; j < i; j++ {
diff := nums[i] - nums[j] + 500
length := dp[j][diff] + 1
if length < 2 {
length = 2
}
if length > dp[i][diff] {
dp[i][diff] = length
}
if dp[i][diff] > ans {
ans = dp[i][diff]
}
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(n^2)$，枚举所有有序下标对
(j, i)。- 空间复杂度：$O(nV)$，其中公差值域 $V = 1001$；在本题固定约束下可视为 $O(n)$。
关键点总结
- 子序列 DP 要保留下标顺序，因此状态必须钉住结尾位置，不能先排序。
- 只记录结尾还不够；同一结尾、不同公差的序列不能互相转移。
- 任意两个元素都能构成等差序列，因此不存在旧状态时长度从 2 起。
- 固定数组依赖题目值域；值域扩大时应改用
Map<公差, 长度>。- 面试追问若把公差固定为给定值，状态可以压缩成「数值 → 最长长度」的一张哈希表，时间降为 $O(n)$。
易错点总结
- 对数组排序：会改变子序列的原下标顺序。
- 公差不加偏移量：负公差会产生负下标。
- 缺省长度从 1 而非最终候选 2 处理错误：两元素序列会被低估。
- 更新同一状态时直接覆盖：多个前驱可能到达同一
(i, d)，必须取最大值。- 照搬 1001 大小却忽略题目值域：只有
nums[i]位于[0, 500]时该下标范围才安全。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 300. 最长递增子序列 | 中等 | 只需钉住结尾一维，且能用贪心加二分优化到对数级 |
| 446. 等差数列划分 II - 子序列 | 困难 | 求方案计数而非长度，需处理「弱等差」状态的累加 |
| 873. 最长的斐波那契子序列的长度 | 中等 | 递推关系依赖前两项之和，状态要记录最后两个下标 |
| 1218. 最长定差子序列 | 中等 | 公差由题目给定，状态降到一维，单次线性扫描即可 |
| 368. 最大整除子集 | 中等 | 相邻约束换成整除关系，需排序后按结尾转移并回溯路径 |