577，数组中的最长连续子序列

Original 博哥数据结构和算法 2022-05-19

There’s room for sentiment but not sentimentality.

可以有感情，但不能感情用事。

问题描述

来源：牛客题霸第95题

难度：中等

给定无序数组arr，返回其中最长的连续序列的长度(要求值连续，位置可以不连续,例如 3,4,5,6为连续的自然数）

示例1

输入：[100,4,200,1,3,2]
返回值：4

示例2

输入：[1,1,1]
返回值：1

提示：

0 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9

先排序

因为数组是无序的，如果要想找出最长的连续序列（这里序列的顺序可以打乱），我们最容易想到的就是先对数组进行排序，然后再查找。

使用一个变量count来记录当前有序序列的长度。

如果当前元素比前一个大1，说明他们可以构成连续的序列，count就加1。
如果相等就跳过。
否则就不能构成连续的序列，count要重置为1，要重新统计。

原理比较简单，我们来看下代码

 1public int MLS(int[] arr) {
 2    if (arr == null || arr.length == 0)
 3        return 0;
 4    int longest = 1;//记录最长的有序序列
 5    int count = 1;//目前有序序列的长度
 6    //先对数组进行排序
 7    Arrays.sort(arr);
 8    for (int i = 1; i < arr.length; i++) {
 9        //跳过重复的
10        if (arr[i] == arr[i - 1])
11            continue;
12        //比前一个大1，可以构成连续的序列，count++
13        if ((arr[i] - arr[i - 1]) == 1) {
14            count++;
15        } else {
16            //没有比前一个大1，不可能构成连续的，
17            //count重置为1
18            count = 1;
19        }
20        //记录最长的序列长度
21        longest = Math.max(longest, count);
22    }
23    return longest;
24}

时间复杂度：O（nlog(n)），排序的复杂度是nlog(n)，for循环是n，相加是nlog(n)+n，所以时间复杂度是nlog(n)。

空间复杂度：O（1），就使用两个变量

使用集合Set解决

如果不排序的话，我们可以先把数组中的元素全部放到集合set中，然后再查找。假如有最长连续序列

x，x+1，x+2……x+n

我们只有从x往后查找才能找出最长的序列，因为从x+1往后查找的有序序列长度肯定是小于从x往后查找的有序序列长度的。

明白了这点，代码就容易写了，我们需要从有序序列的最小值开始计算即可，来看下代码

 1public int MLS(int[] arr) {
 2    //先把数组放到集合set中
 3    Set<Integer> set = new HashSet<>();
 4    for (int num : arr)
 5        set.add(num);
 6    int longest = 0;//记录最长的有序序列
 7    for (int num : arr) {
 8        //这里要找有序序列最小的元素（不一定是最长
 9        //有序序列的）。如果还有更小的，说明当前元素
10        //不是最小的，直接跳过
11        if (set.contains(num - 1))
12            continue;
13        //说明当前元素num是当前序列中最小的元素（这里
14        //的当前序列不一定是最长的有序序列）
15        int currentNum = num;
16        //统计当前序列的长度
17        int count = 1;
18        while (set.contains(currentNum + 1)) {
19            currentNum++;
20            count++;
21        }
22        //保存最长的值
23        longest = Math.max(longest, count);
24    }
25    return longest;
26}