#1218 最长定差子序列(哈希表|动态规划)

1218. 最长定差子序列 - 力扣（LeetCode）

非优化纯动规查找：

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int n=arr.size();
        vector<int> dp(n,1);
        int gmax=(int)(arr.size()>0);
        for(int i=1;i<n;i++){
            int j=i-1;
            while(j>=0){
                if(arr[j]==arr[i]-difference) break;
                j--; 
            }
            if(j>=0)
                dp[i]+=dp[j];
            if(dp[i]>gmax) gmax=dp[i];
        }
        return gmax;
    }
};

超时，原因在于查找arr[i]-difference使时间复杂度达到N^2

使用哈希表优化查找：

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int n=arr.size();
        vector<int> dp(n,1);
        unordered_map<int,int> hmap;
        hmap[arr[0]]=1;
        int gmax=(int)(arr.size()>0);
        for(int i=1;i<n;i++){
            if(hmap.find(arr[i]-difference) != hmap.end())
                dp[i]+=hmap[arr[i]-difference];
            hmap[arr[i]]=dp[i];
            if(dp[i]>gmax) gmax=dp[i];
        }
        return gmax;
    }
};