题解 | #数组中的最长连续子序列#

思路1：去重 + 排序

class Solution {
public:
    /**
     * max increasing subsequence
     * @param arr int整型vector the array
     * @return int整型
     */
    int MLS(vector<int>& arr) {
        // write code here
        if(arr.size() == 1){
            return 1;
        }
        unordered_map<int, int> tb;
        for(int i=0; i<arr.size(); i++){
            tb[arr[i]] += 1;
        }
        vector<int> data;
        for(auto it=tb.begin(); it!=tb.end(); it++){
            data.push_back(it->first);
        }
        
        sort(data.begin(), data.end());
        int res = 1;
        int left=0, right=1;
        while(right < data.size()){
            while(right < data.size() && data[right] == data[right-1]+1){
                right++;
            }
            res = max(res, right-left);
            left = right;
            right++;
        }
        return res;
    }
};

思路2：使用集合 参考：https://leetcode-cn.com/problems/longest-consecutive-sequence/solution/zui-chang-lian-xu-xu-lie-by-leetcode-solution/

class Solution {
public:
    int MLS(vector<int>& nums) {
        unordered_set<int> num_set;
        for (const int& num : nums) {
            num_set.insert(num);
        }

        int longestStreak = 0;

        for (const int& num : num_set) {
            if (!num_set.count(num - 1)) {
                int currentNum = num;
                int currentStreak = 1;

                while (num_set.count(currentNum + 1)) {
                    currentNum += 1;
                    currentStreak += 1;
                }

                longestStreak = max(longestStreak, currentStreak);
            }
        }

        return longestStreak;           
    }
};