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

题意整理：
求数组中的最长连续子序列，即求得能够满足连续的数字的最长序列长度。
解法1：
思路：
由题可知，我们首先要做的就是排序，由于C++自带的排序函数比冒泡排序快很多，故我们直接使用sort函数。
图解：
图片说明
然后有三种情况：

当前数比前一个数大1，刚好能构成连续序列，计数变量加1；
当前数与前一个数相等，故此数可以直接跳过；
当前数与前一个数的差超过1，无法构成连续序列，则计数变量需要置为0，重新开始统计连续序列的长度。

代码：

class Solution {
public:
    /**
     * max increasing subsequence
     * @param arr int整型vector the array
     * @return int整型
     */
    int MLS(vector<int>& arr) {
     sort(arr.begin(),arr.end());
        int ans=0;
        int count=1;
        for(int i=0;i<arr.size()-1;i++){
            if(arr[i]==arr[i+1])//遇到重复的数
            {
                continue;
            }
            if((arr[i]+1==arr[i+1]))//遇到可以加入序列的数
            {
                count++;
            }
           else{//遇到间隔大于1的数
               count=1;
               }
             if(ans<count){
                   ans=count;}//选出最大序列长度
        }
        return ans ;
    }
};

复杂度分析:
时间复杂度： $O(nlogn)$ ；排序复杂度是 $O(nlogn)$ ，循环体复杂度是 $O(n)$ ，故算法的时间复杂度是 $O(nlogn)$ ；
空间复杂度： $O(1)$ ；由于输入数据量是常数，故空间复杂度是 $O(1)$ 。

解法2：
思路：
不进行排序，将全部元素放入集合中，如果有一个最长连续子序列， $x_1,x_2,...,x_n$ (序列间隔为1)；则 $x_1$ 一定是符合条件的最小的，若 $x_1-1$ 在集合中，则解变为 $x_1-1,x_1,x_2,...,x_n$ ；
所以先判断 $x_1-1$ 是不是在集合中，若在，接着判断 $x_1-1-1$ ;若不在,则直接找 $x_1+1$ ;以此类推。直到找到一个序列结束，与最长的进行比较。

代码：

import java.util.*;


public class Solution {
    /**
     * max increasing subsequence
     * @param arr int整型一维数组 the array
     * @return int整型
     */
    public int MLS (int[] arr) {
        // write code here
        Set<Integer> set=new HashSet<>();
        for(int num : arr)
            set.add(num);//将数组存入集合中
        int longest =0;
        for(int num :arr){
            if(set.contains(num -1))//集合当中有比当前数小1的数
                continue;
            int currentNum =num;
            int count =1;
            while(set.contains(currentNum +1)){//集合当中有比当前数大1的数
                currentNum++;
                count++;
            }
            longest = Math.max(longest,count);
        }
        return longest;
    }
}

复杂度分析：
时间复杂度： $O(n)$ ,循环体的复杂度最高为 $O(n)$ ;
空间复杂度： $O(n)$ ,使用集合存储数组元素，空间复杂度为 $O(n)$ 。