《数组中的最长连续子序列》

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

例如：输入：[100,4,200,1,3,2]
那么很明显我们能够知道1234这是连续的，所以最长的子序列则为4。

所以这道题目的关键就是找到连续的子序列。

方法一：使用set集合
因为我们要找到连续的子序列，比较容易的想法就是找到那个连续子序列中最小的那个数字，然后利用这个最小的数字依次递增1，去查看说有没有对应的数，有的话则继续，直到没有的话则算出此时最长的连续子序列。

那么如何找出连续子序列中最小的那个数字呢？其实很简单，我们只需要判断有无比当前数小1的数即可。
例如：当前数为 5，我如何判断5是否是连续子序列最小的那个呢？就是判断说所有数字中有没有4，如果没有，则5就是以5开始的连续子序列的最小的那个数字了。
所以，根据上面的需求，我们每次都要判断有无该数，很容易想到set集合中的contains方法。
图片说明
下面直接来看代码~

public int MLS (int[] arr) {
        //先判断arr的长度是否合法
        if(arr.length <= 0){
            return 0;
        }
        // 创建一个set集合然后将所有的数存进去
        HashSet<Integer> set = new HashSet<>();
        for(int num:arr){
            set.add(num);
        }
        int maxLen = 0; // 存储长度
        for(int i = 0; i < arr.length; i++){
            // 这里就是找出一个连续子序列中最小的那个数字！
            if(set.contains(arr[i]-1))
                continue;
            // 当作起点
            int start = arr[i];
            // 当集合中有start+1这个数，则递增+1继续寻找
            while(set.contains(start+1)){
                start++;
            }
            // while循环结束，此时已经找到一个以arr[1]为起点，start为终点的连续子序列了
            // 所以 start-arr[i]+1 算出长度。（假设 2为起点，5为终点，长度则为5-2+1=4）
            maxLen = Math.max(maxLen,start-arr[i]+1);
        }
        // 返回最长的长度！
        return maxLen;
    }

复杂度分析：
时间复杂度: $O(n)$ , 循环的次数为数组的长度n。
空间复杂度: $O(n)$ , set集合的空间。

方法二：排序
我们也可以换个方法，先排序，然后在遍历的时候我们就可以去找到连续子序列然后去统计出最长的那个了。
所以就将题目转变为，在排序数组中找到最长的连续序列。则只需要遍历一遍即可找到结果！
图片说明

public int MLS (int[] arr) {
        // write code here
        if(arr.length <= 0){
            return 0;
        }
        int maxLen = 0; //记录长度
        int cnt = 1; // 计数，计算此时子序列的长度
        // 使用sort函数进行排序
        Arrays.sort(arr);
        for(int i = 1; i < arr.length; i++){
            // 去除重复的数字，定位到当前数字的前一个与当前数不等
            if(arr[i] == arr[i-1]) continue;
            // 如果前一个数跟当前数相差1，则cnt计数+1
            if(arr[i]-arr[i-1] == 1){
                cnt++;
            }else{
                // 否则则不能构成连续子序列，所以cnt复位。
                cnt = 1;
            }
            // 是否需要更新，取决于cnt与原来长度比较
            maxLen = Math.max(maxLen,cnt);
        }
        // 返回最长的
        return maxLen;
    }

复杂度分析：
时间复杂度: $O(NlogN)$ , sort函数的时间复杂度。
空间复杂度: $O(1)$ , 没有使用额外的空间。