LeetCode挑战：1218.最长固定差值子序列（等差数列变种）

问题描述

给定一个整数数组 arr 和一个整数 difference，任务是找出数组中最长的等差数列子序列，其中等差数列的公差等于给定的 difference。

解题思路

这个问题可以通过动态规划来解决。基本思路是使用一个数组 dp 来记录到当前位置为止，以该位置元素结尾的最长等差数列的长度。然而，直接应用类似最长递增子序列（LIS）的方法会导致较高的时间复杂度 O(N^2)，这对于大数据集来说是不可接受的。

与LIS问题相比，本题的关键在于等差数列的特性使得我们可以更高效地更新状态。在LIS中，我们需要遍历所有之前的元素来确定当前元素是否能加入到已有的序列中，而在等差数列中，只要前一个元素满足等差条件，我们就可以直接继承其状态，从而大大减少了不必要的计算。

代码实现

初始动态规划解法

尽管直接使用动态规划可以解决问题，但这种方法的时间复杂度过高。以下是基本的动态规划实现：

class Solution { public: int longestSubsequence(vector& arr, int difference) { int n = arr.size(); vector dp(n, 1); for (int i = 1; i 

优化后的动态规划解法

为了提高效率，我们可以通过哈希表来记录每个元素作为等差数列结尾时的最大长度。这样，每次只需要检查当前元素减去公差后的元素是否存在即可，从而将时间复杂度降低至 O(N)。

class Solution { public: int longestSubsequence(vector& arr, int difference) { int n = arr.size(); unordered_map dp; int maxLength = 1; for (int i = 0; i 

这种优化方法利用了等差数列的性质，避免了重复计算，显著提高了算法的性能。