1027. 最长等差数列

🟠   🔖  数组 哈希表 二分查找 动态规划  🔗 力扣 LeetCode

题目

Given an array nums of integers, return the length of the longest arithmetic subsequence in nums.

Note that:

• A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
• A sequence seq is arithmetic if seq[i + 1] - seq[i] are all the same value (for 0 <= i < seq.length - 1).

Example 1:

Input: nums = [3,6,9,12]

Output: 4

Explanation: The whole array is an arithmetic sequence with steps of length = 3.

Example 2:

Input: nums = [9,4,7,2,10]

Output: 3

Explanation: The longest arithmetic subsequence is [4,7,10].

Example 3:

Input: nums = [20,1,15,3,10,5,8]

Output: 4

Explanation: The longest arithmetic subsequence is [20,15,10,5].

Constraints:

• 2 <= nums.length <= 1000
• 0 <= nums[i] <= 500

题目大意

给你一个整数数组 nums，返回 nums 中最长等差子序列的长度 。

回想一下，nums 的子序列是一个列表 nums[i1], nums[i2], ..., nums[ik] ，且 0 <= i1 < i2 < ... < ik <= nums.length - 1。并且如果 seq[i+1] - seq[i]( 0 <= i < seq.length - 1) 的值都相同，那么序列 seq 是等差的。

示例 1：

输入： nums = [3,6,9,12]

输出： 4

解释：

整个数组是公差为 3 的等差数列。

示例 2：

输入： nums = [9,4,7,2,10]

输出： 3

解释：

最长的等差子序列是 [4,7,10]。

示例 3：

输入： nums = [20,1,15,3,10,5,8]

输出： 4

解释：

最长的等差子序列是 [20,15,10,5]。

提示：

• 2 <= nums.length <= 1000
• 0 <= nums[i] <= 500

解题思路

1. 定义状态 dp[i][diff]

   • dp[i][diff] 代表 以 nums[i] 结尾，公差为 diff 的最长等差子序列的长度。
   • 我们用 哈希表 Map 代替二维数组 来存储 (i, diff) -> 长度 关系，减少不必要的存储。

2. 状态转移方程

   • 枚举 j < i，计算 diff = nums[i] - nums[j]：
     • 若 dp[j][diff] 存在，则 dp[i][diff] = dp[j][diff] + 1
     • 否则，dp[i][diff] = 2（默认至少包含 nums[j] 和 nums[i]）

3. 优化

   • 由于 dp[i][diff] 只依赖于 dp[j][diff]，我们 直接用 Map 存储 (索引 i, 公差 diff) -> 最长长度。
   • 这样可以 避免 O(n^2) 级别的二维数组存储开销，提升空间效率。

复杂度分析

• 时间复杂度：O(n^2)，需要两层循环遍历所有 (i, j) 组合。
• 空间复杂度：O(n * d)，其中 d 是 nums[i] - nums[j] 的取值范围，通常小于 O(n^2)，相比 dp[i][diff] 方式更节省空间。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestArithSeqLength = function (nums) {
	const n = nums.length;
	if (n <= 2) return n;

	let maxLen = 2;
	const dp = new Map(); // 只存储实际的 (索引, 差值) 组合

	for (let i = 0; i < n; i++) {
		for (let j = 0; j < i; j++) {
			const diff = nums[i] - nums[j];
			const key = `${i},${diff}`; // 组合索引和公差
			dp.set(key, (dp.get(`${j},${diff}`) || 1) + 1);
			maxLen = Math.max(maxLen, dp.get(key));
		}
	}
	return maxLen;
};

相关题目

题号	标题	题解	标签	难度	力扣
2453	摧毁一系列目标		数组 哈希表 计数	🟠	🀄️ 🔗