1218. 最长定差子序列

🟠   🔖  数组 哈希表 动态规划  🔗 力扣 LeetCode

题目

Given an integer array arr and an integer difference, return the length of the longest subsequence in arr which is an arithmetic sequence such that the difference between adjacent elements in the subsequence equals difference.

A subsequence is a sequence that can be derived from arr by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: arr = [1,2,3,4], difference = 1

Output: 4

Explanation: The longest arithmetic subsequence is [1,2,3,4].

Example 2:

Input: arr = [1,3,5,7], difference = 1

Output: 1

Explanation: The longest arithmetic subsequence is any single element.

Example 3:

Input: arr = [1,5,7,8,5,3,4,2,1], difference = -2

Output: 4

Explanation: The longest arithmetic subsequence is [7,5,3,1].

Constraints:

• 1 <= arr.length <= 10^5
• -10^4 <= arr[i], difference <= 10^4

题目大意

给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差等于 difference 。

子序列 是指在不改变其余元素顺序的情况下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

示例 1：

输入： arr = [1,2,3,4], difference = 1

输出： 4

解释： 最长的等差子序列是 [1,2,3,4]。

示例 2：

输入： arr = [1,3,5,7], difference = 1

输出： 1

解释： 最长的等差子序列是任意单个元素。

示例 3：

输入： arr = [1,5,7,8,5,3,4,2,1], difference = -2

输出： 4

解释： 最长的等差子序列是 [7,5,3,1]。

提示：

• 1 <= arr.length <= 10^5
• -10^4 <= arr[i], difference <= 10^4

解题思路

1. 使用哈希表 dp

   • dp[num] 表示 以 num 结尾的最长等差子序列的长度。
   • 这样可以快速查询 num - difference 对应的子序列长度，避免 O(n^2) 的双层循环。

2. 遍历 arr 构建 dp

   • 对于 arr[i] = num，如果 num - difference 存在于 dp，则可以接在 num - difference 之后形成更长的等差子序列：

     dp.set(num, (dp.get(num - difference) || 0) + 1);
     

   • 维护 maxLen 记录最长等差子序列的长度。

3. 返回 maxLen 作为最终结果

   • 遍历完数组后，maxLen 记录的是最长等差子序列的长度。

复杂度分析

• 时间复杂度：O(n)，因为每个元素在 Map 中只进行 O(1) 查询和更新操作。
• 空间复杂度：O(n)，最坏情况下 Map 需要存储所有 arr[i]。

代码

/**
 * @param {number[]} arr
 * @param {number} difference
 * @return {number}
 */
var longestSubsequence = function (arr, difference) {
	const dp = new Map();
	let maxLen = 1;
	for (let num of arr) {
		dp.set(num, (dp.get(num - difference) || 0) + 1);
		maxLen = Math.max(maxLen, dp.get(num));
	}
	return maxLen;
};

相关题目

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