思路：

题目的主要信息：

数组无序，且有重复
需要找连续最长子序列长度，且连续不必相邻

方法一：排序法

既然无序我们可以用排序来解决。

具体做法：

使用sort的快排，将序列排成递增序列。然后遍历数组，依次将其与前一个数比较，若是比前一个大1，则连续子序列增加1；若是与前一个一样大，需要不管直接进入下一循环（去重）；若是比前一个大超过1，则连续断掉，重新计数，同时比较并更新最大值。

class Solution {
public:
    int MLS(vector<int>& arr) {
        sort(arr.begin(), arr.end()); //排序
        int n = arr.size(); 
        int max_len = 1, len = 1;
        for (int i = 1; i < n; i++) {  //逐一比较该数与前一个数
            if (arr[i] == arr[i - 1] + 1) 
                len++;
            else if (arr[i] == arr[i - 1])  //若是相等，则跳过
                continue;
            else {
                max_len = max(max_len, len);
                len = 1;
            }
        }
        return max(max_len, len); //防止最后一个数字重复，跳过了上面的最大值比较
    }
};

复杂度分析：

时间复杂度：O(ngln)，快速排序的时间复杂度
空间复杂度：O(1)，没有额外空间

方法二：哈希表

同时我们也可以使用哈希表的快速访问加上集合的思想来解决。

具体做法：

设置一个哈希表，key值表示所在位置的最长连续序列的长度。每当我们遍历数组时，若是该数字应该出现在表中了，说明重复，继续往后，去重；若是没有出现过，我们就比较该数字的前一个数字和后一个数字是否出现在了哈希表中，如果有，我们用集合的思想将其合并为一个集合，更新哈希表中的长度只需要更新这个集合首位的长度即可，因为中间的已经不会再有统计了。随着集合中元素越来越多，必然是连续的子序列增多，每次比较哈希表中的值即可得到最大值。图片说明

class Solution {
public:
    int max_len = 1;
    unordered_map<int, int> hash; //哈希表，key值表示所在位置的最长连续序列的长度
    void merge(int less, int more) {  //将相邻的数合并
        int left = less - hash[less] + 1;
        int right = more + hash[more] - 1;
        int len = right - left + 1;
        if (len > max_len) 
            max_len = len;
        hash[left] = hash[right] = len;
}
    int MLS(vector<int>& arr) {
        int n = arr.size(); 
        for(int i = 0; i < n; i++){
            if (!hash.count(arr[i])) {  //去重
                hash[arr[i]] = 1;
                //分别检查哈希表中是否有arr[i] - 1和arr[i] + 1
                if (hash.count(arr[i] - 1)) 
                    merge(arr[i] - 1, arr[i]);//合并
                if (hash.count(arr[i] + 1)) 
                    merge(arr[i], arr[i] + 1);
            }
        }
        return max_len; 
    }
};

复杂度分析：

时间复杂度：O(n)，哈希访问每次为O(1)，一共一个遍历循环
空间复杂度：O(n)，哈希表最大空间

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

思路：