1027. 最长等差数列
题目描述
输入整数数组 nums，返回其中最长等差子序列的长度。
子序列是从数组中删掉若干元素（也可以不删）后剩下的序列，剩余元素保持原来的先后顺序，不要求连续。
若序列中每对相邻元素之差都相等，就称它是等差的，公差可以为负数或 0。
示例 1
输入：nums = [3,6,9,12] 输出：4
解释：整个数组公差为 3，长度 4。
示例 2
输入：nums = [9,4,7,2,10] 输出：3
解释：[4,7,10] 公差为 3，找不到长度为 4 的。
示例 3
输入：nums = [20,1,15,3,10,5,8] 输出：4
解释：[20,15,10,5] 公差为 -5，长度 4。
数据范围
2 <= nums.length <= 15000 <= nums[i] <= 500
解题思路：哈希表 DP（以结尾和公差为状态）
一个等差子序列由“结尾位置 + 公差”确定。设 dp[i][d] 为以 nums[i] 结尾、公差为 d 的最长长度。枚举前一个元素 j < i，d = nums[i] - nums[j]：如果以 j 结尾已有公差 d 的序列，就接上去，长度 dp[j][d] + 1；否则 j、i 两个数自成一个长度 2 的序列。答案是所有 dp 值的最大值。公差用哈希表存，或因为取值在 [-500,500]，加偏移 500 用数组。
为什么正确
处理完 i 的所有 j 后，dp[i] 里每个公差 d 对应以 nums[i] 结尾、公差 d 的最长长度。
复杂度分析
时间 O(n²)，空间 O(n²) 或 O(n·V)（V = 1001）。
易错点
找不到 dp[j][d] 时长度是 2（j 和 i 两个数），不是 1。不要用“先排序”，子序列必须保持原顺序。公差可以是负数或 0。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def longestArithSeqLength(self, nums: List[int]) -> int:
n = len(nums)
dp = [dict() for _ in range(n)]
ans = 2
for i in range(1, n):
for j in range(i):
d = nums[i] - nums[j]
cur = dp[j].get(d, 1) + 1
if cur > dp[i].get(d, 0):
dp[i][d] = cur
ans = max(ans, cur)
return ansclass Solution {
public int longestArithSeqLength(int[] nums) {
int n = nums.length;
int[][] dp = new int[n][1001];
int ans = 2;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
int d = nums[i] - nums[j] + 500;
int cur = Math.max(dp[j][d], 1) + 1;
if (cur > dp[i][d]) {
dp[i][d] = cur;
}
ans = Math.max(ans, cur);
}
}
return ans;
}
}class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> dp(n, vector<int>(1001, 0));
int ans = 2;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
int d = nums[i] - nums[j] + 500;
int cur = max(dp[j][d], 1) + 1;
if (cur > dp[i][d]) {
dp[i][d] = cur;
}
ans = max(ans, cur);
}
}
return ans;
}
};func longestArithSeqLength(nums []int) int {
n := len(nums)
dp := make([][1001]int, n)
ans := 2
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
d := nums[i] - nums[j] + 500
cur := max(dp[j][d], 1) + 1
if cur > dp[i][d] {
dp[i][d] = cur
}
ans = max(ans, cur)
}
}
return ans
}var longestArithSeqLength = function(nums) {
const n = nums.length;
const dp = Array.from({ length: n }, () => new Map());
let ans = 2;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
const d = nums[i] - nums[j];
const cur = (dp[j].get(d) || 1) + 1;
if (cur > (dp[i].get(d) || 0)) {
dp[i].set(d, cur);
}
ans = Math.max(ans, cur);
}
}
return ans;
};function longestArithSeqLength(nums: number[]): number {
const n = nums.length;
const dp = Array.from({ length: n }, () => new Map<number, number>());
let ans = 2;
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
const d = nums[i] - nums[j];
const cur = (dp[j].get(d) || 1) + 1;
if (cur > (dp[i].get(d) || 0)) {
dp[i].set(d, cur);
}
ans = Math.max(ans, cur);
}
}
return ans;
}其他解法
主解法枚举数对 (j, i) 自然得到公差，复杂度只与 n 有关；枚举公差的做法把问题拆成 2V 个简单的一维 DP，复杂度与值域有关，适合值域很小的情况。
解法 2：枚举公差 + 值域 DP 时间 O(n · V)，V 为值域大小，空间 O(V)
公差 d 的取值范围是 [-(max-min), max-min]。对每个固定的 d 单独求一遍最长等差子序列：从左到右扫描，f[v] 表示到目前为止以值 v 结尾、公差为 d 的最长长度。读到 x 时，它只能接在值为 x - d 的元素后面，所以 f[x] = f[x - d] + 1（x - d 超出值域时为 1）。同一个值后出现时直接覆盖，因为越靠后的长度只会更长。
每一轮只用一个长度为值域的数组，内存很小，没有哈希表开销。当值域远大于 n 时不适用，本题值域只有 0 到 500 才可行。
class Solution:
def longestArithSeqLength(self, nums: List[int]) -> int:
lo, hi = min(nums), max(nums)
span = hi - lo
ans = 1
for d in range(-span, span + 1):
f = [0] * (span + 1)
for x in nums:
v = x - lo
y = v - d
cur = f[y] + 1 if 0 <= y <= span else 1
f[v] = cur
if cur > ans:
ans = cur
return ansclass Solution {
public int longestArithSeqLength(int[] nums) {
int lo = Integer.MAX_VALUE, hi = Integer.MIN_VALUE;
for (int x : nums) {
lo = Math.min(lo, x);
hi = Math.max(hi, x);
}
int span = hi - lo, ans = 1;
int[] f = new int[span + 1];
for (int d = -span; d <= span; d++) {
Arrays.fill(f, 0);
for (int x : nums) {
int v = x - lo, y = v - d;
int cur = (y >= 0 && y <= span) ? f[y] + 1 : 1;
f[v] = cur;
ans = Math.max(ans, cur);
}
}
return ans;
}
}class Solution {
public:
int longestArithSeqLength(vector<int>& nums) {
int lo = *min_element(nums.begin(), nums.end());
int hi = *max_element(nums.begin(), nums.end());
int span = hi - lo, ans = 1;
vector<int> f(span + 1);
for (int d = -span; d <= span; d++) {
fill(f.begin(), f.end(), 0);
for (int x : nums) {
int v = x - lo, y = v - d;
int cur = (y >= 0 && y <= span) ? f[y] + 1 : 1;
f[v] = cur;
ans = max(ans, cur);
}
}
return ans;
}
};func longestArithSeqLength(nums []int) int {
lo, hi := nums[0], nums[0]
for _, x := range nums {
lo = min(lo, x)
hi = max(hi, x)
}
span, ans := hi-lo, 1
f := make([]int, span+1)
for d := -span; d <= span; d++ {
for i := range f {
f[i] = 0
}
for _, x := range nums {
v := x - lo
y := v - d
cur := 1
if y >= 0 && y <= span {
cur = f[y] + 1
}
f[v] = cur
ans = max(ans, cur)
}
}
return ans
}var longestArithSeqLength = function(nums) {
const lo = Math.min(...nums), hi = Math.max(...nums);
const span = hi - lo;
let ans = 1;
const f = new Int32Array(span + 1);
for (let d = -span; d <= span; d++) {
f.fill(0);
for (const x of nums) {
const v = x - lo, y = v - d;
const cur = (y >= 0 && y <= span) ? f[y] + 1 : 1;
f[v] = cur;
if (cur > ans) ans = cur;
}
}
return ans;
};function longestArithSeqLength(nums: number[]): number {
const lo = Math.min(...nums), hi = Math.max(...nums);
const span = hi - lo;
let ans = 1;
const f = new Int32Array(span + 1);
for (let d = -span; d <= span; d++) {
f.fill(0);
for (const x of nums) {
const v = x - lo, y = v - d;
const cur = (y >= 0 && y <= span) ? f[y] + 1 : 1;
f[v] = cur;
if (cur > ans) ans = cur;
}
}
return ans;
}