[数据结构与算法]牛客-NC95-数组中的最长连续子序列

方法一：排序

写在前面：这道题是剑指Offer II 119. 最长连续序列，也是LeetCode 128. 最长连续序列，字节一二面也考了这道题。
思路：
被这道题唬住了，其实暴力也能解，思路是排序+计数。循环遍历数组，分为以下情况：

1. 当前值和前一个值相等，则跳过本次循环。
2. 当前值和前一个值刚好符合连续，即长度差为1，则计数加一。
3. 否则，让计数为1（重新开始）。
4. 更新最长的长度。
   可以写出以下代码：

public int MLS (int[] arr) {
    // write code here
    if (arr == null || arr.length == 0) {
        return 0;
    }
    Arrays.sort(arr);
    int _mls = -1;
    int count = 0;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] == arr[i - 1]) continue;
        if (arr[i] - arr[i - 1] == 1) {
            count = count + 1;
        } else {
            count = 1;
        }
        _mls = Math.max(_mls, count);
    }
    return _mls;
}

时间复杂度： O(n * log(n))，函数库快排时间复杂度为O(n * log(n)), 循环遍历的时间复杂度为O(n)。
空间复杂度： O(1)，除开几个必须的指针，并未使用其他空间。