1218.最长定差子序列 (Medium)*

题目描述*

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

示例*

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

输出：4

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

输出：4

提示*

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

代码*

一看就是个 dp，可以根据最长递增子序列的思路写。但是超时了，这就需要优化，可以先用 map<int, vector\> 优化，保存每个值的位置，优化时按照 arr[i] - difference 获取位置。但是优化后速度还是比较慢。

其实可以直接用 unordered_map 将出现过的元素记录下来，值表示包含其键所能构成的最长序列。

dp 超时dp 优化unordered_map

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

class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int len = arr.size();
        vector<int> dp(len, 1);
        unordered_map<int, vector<int>> posMap;
        for(int i = 0; i < len; i++) {
            posMap[arr[i]].push_back(i);
        }
        int res = 1;
        for(int i = 1; i < len; i++) {
            if(posMap.count(arr[i] - difference)) {
                for(auto j : posMap[arr[i] - difference]) {
                    if(j < i) {
                        dp[i] = max(dp[i], dp[j] + 1);
                    }
                }
            }
            res = max(res, dp[i]);
        }
        return res;
    }
};

class Solution {
private:
    unordered_map<int, int> posMap;
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int res = 0;
        for(auto i : arr) {
            // posMap[i] = posMap[i - difference] + 1;
            res = max(res, posMap[i] = posMap[i - difference] + 1);
        }
        return res;
    }
};

最后更新: July 23, 2022