[NC]95. 数组中的最长连续子序列

🚩传送门：牛客题目
力扣题目

题目

给定无序数组，返回其中最长的连续序列的长度(要求值连续，位置可以不连续）。

例如 **3,4,5,6** 为连续的自然数

要求：空间复杂度 ，时间复杂度

解题思路：排序

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

复杂度分析

时间复杂度： ，该方法需要遍历一次数组所有元素，但是需要一次排序数组 。

空间复杂度： ，该方法使用常数空间 。

我的代码

public class Solution {
     public int MLS(int[] arr) {
        if (arr == null || arr.length == 0)
            return 0;
        int longest = 1;//记录最长的有序序列
        int count = 1;//目前有序序列的长度
        //先对数组进行排序
        Arrays.sort(arr);
        for (int i = 1; i < arr.length; i++) {
            //跳过重复的
            if (arr[i] == arr[i - 1])
                continue;
            //比前一个大1，可以构成连续的序列，count++
            if ((arr[i] - arr[i - 1]) == 1) {
                count++;
            } else {
                //没有比前一个大1，不可能构成连续的，
                //count重置为1
                count = 1;
            }
            //记录最长的序列长度
            longest = Math.max(longest, count);
        }
        return longest;
    }
}

解题思路：哈希表

一个数字连续序列是不包含重复的数字的，所以使用 去重。

为了保证的时间复杂度，避免重复枚举一段序列，我们要从序列的起始数字向后枚举。也就是说如果有一个的连续序列，我们只会以为起点向后枚举，而不会从向后枚举。

如何保证只会以为起点向后枚举？
其实只需要每次在哈希表中检查是否存在即可。如果存在，说明当前数不是连续序列的起始数字，我们跳过这个数。

复杂度分析

时间复杂度： ，其中 为数组的长度，该方法需要遍历一次数组所有元素 。

空间复杂度： ，哈希表存储数组中所有的数需要 的空间。

我的代码

class Solution {
    public static int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        HashSet<Integer> set = new HashSet<>();
        // HashSet 去重
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
        }
        int res=0;
        for (int num : set) {
            int count = 0;
            if (set.contains(num - 1)) continue;
            else{
                // 统计起始序列长度
                while(set.contains(num++)) count++;
                res= Math.max(count,res);
            }
        }
        return res;
    }
}