力扣题解（ 最长定差子序列）

1218. 最长定差子序列
给你一个整数数组 arr 和一个整数 difference，请你找出并返回 arr 中最长等差子序列的长度，该子序列中相邻元素之间的差便是 difference 。
子序列 是指在不改变别的元素次序的环境下，通过删除一些元素或不删除任何元素而从 arr 派生出来的序列。

思绪：
本题的思绪很简单，规定dp是包罗i位置元素的最长定差子序列，此时只须要确认在（0-i-1）位置中是否存在一个下标j，是的i位置元素减j位置元素仍时diffenence，则此时dp=dp[j]+1.本题的优化是使用哈希表，存放已经求出最长定差子序列的元素和对应的下标，如允许以在O（1）时间内查找（0-i-1）中是否存在值为arr-difference的元素。

1. class Solution {
2. public:
3.     int longestSubsequence(vector<int>& arr, int difference) {
4.      
5.      int n=arr.size();
6.      vector<int>dp(n,1);
7.      unordered_map<int,int>hash;
8.      hash[arr[0]]=0;
9.      for(int i=1;i<n;i++)
10.      {
11.         if(hash.count(arr[i]-difference))
12.         {
13.             dp[i]=dp[hash[arr[i]-difference]]+1;
14.         }
15.         hash[arr[i]]=i;
16.      }
17.      
18.      int ret=0;
19.      for(auto e:dp)
20.      {
21.         ret=max(ret,e);
22.      }
24.      return ret;
26.     }
27. };

复制代码