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

题目主要信息:

在一个无序数组中，找到最长的连续序列的长度
连续序列是像1、2、3、4这样数值上是连续的序列，位置没有要求，只要存在于数组就行

具体思路:

既然给定的数组无序，我们又要找数值上是连续的序列，那最直观与简单的莫过于排序后，在有序数组中寻找了。

step 1：先用sort函数，对数组进行排序。
step 2：遍历排序后的数组，逐一比较遍历的当前元素与前一个数的大小关系，如果刚好是相差1，则是连续的序列，如果相等需要跳过，去找到它后一个，其他情况则意味着连续断了，维护一个最大值，重新开始记录新一轮的连续子序列。
step 3：为了防止最后一个数字重复，跳过了循环最后一次最大值比较，因此最后还需要再比较一次

遍历图示如下图所示： alt

代码实现:

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 (n l o g_{2} n)$ ，sort函数的复杂度为 $O (n l o g_{2} n)$ ，后续的遍历属于低次幂，略去
空间复杂度： $O (1)$ ，无额外空间