Medium

题目描述

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

子序列是指可以通过删除一些或不删除元素而不改变其余元素顺序得到的序列。

示例 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

解题思路

这是一道动态规划问题，关键在于找到状态转移的规律。

核心思路： 我们用哈希表 dp 来记录以每个数值结尾的等差子序列的最大长度。对于数组中的每个元素 arr[i]，如果要构成等差子序列，那么前一个元素应该是 arr[i] - difference。

状态转移方程：

  • dp[arr[i]] = dp[arr[i] - difference] + 1
  • 如果 arr[i] - difference 不存在，则 dp[arr[i]] = 1

算法步骤：

  1. 遍历数组中的每个元素
  2. 对于当前元素 num，查找 num - difference 是否在哈希表中
  3. 如果存在，则当前元素可以接在以 num - difference 结尾的子序列后面
  4. 更新 dp[num] = dp[num - difference] + 1
  5. 如果不存在，则 dp[num] = 1
  6. 维护全局最大值

这种方法的优势是时间复杂度为 O(n)，空间复杂度为 O(n)，非常高效。

代码实现

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        unordered_map<int, int> dp;
        int maxLen = 1;
        
        for (int num : arr) {
            dp[num] = dp[num - difference] + 1;
            maxLen = max(maxLen, dp[num]);
        }
        
        return maxLen;
    }
};

class Solution:
    def longestSubsequence(self, arr: List[int], difference: int) -> int:
        dp = {}
        max_len = 1
        
        for num in arr:
            dp[num] = dp.get(num - difference, 0) + 1
            max_len = max(max_len, dp[num])
        
        return max_len

public class Solution {
    public int LongestSubsequence(int[] arr, int difference) {
        Dictionary<int, int> dp = new Dictionary<int, int>();
        int maxLen = 1;
        
        foreach (int num in arr) {
            dp[num] = (dp.ContainsKey(num - difference) ? dp[num - difference] : 0) + 1;
            maxLen = Math.Max(maxLen, dp[num]);
        }
        
        return maxLen;
    }
}

var longestSubsequence = function(arr, difference) {
    const dp = new Map();
    let maxLen = 1;
    
    for (const num of arr) {
        dp.set(num, (dp.get(num - difference) || 0) + 1);
        maxLen = Math.max(maxLen, dp.get(num));
    }
    
    return maxLen;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)遍历数组一次，每次哈希表操作为 O(1)
空间复杂度O(n)哈希表最多存储 n 个不同的数值

相关题目