128. 最长连续序列(中等)

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

题目要求O(n)，那么就不能排序，可以使用时间换空间的方式:使用hashSet存储数组，这样查找一个元素的事件可以压缩至O(1)。

public int longestConsecutive(int[] nums) {
        Set<Integer> ss = new HashSet<>();

        for(Integer num:nums){
            ss.add(num);
        }
        int longest = 0;
        for(Integer num:nums){
            if(ss.remove(num)){
                int currentLongest =1;
                int current = num;
                //向左遍历删除
                while(ss.remove(current-1)) current--;
                currentLongest += (num-current);
                
                //向右遍历删除
                current = num;
                while(ss.remove(current +1)) current++;
                currentLongest += (current-num);

                longest = Math.max(longest,currentLongest);
            }
        }
        return longest;
    }

这题还可以使用map记录连续区间长度（动态规划）、使用并查集。。。。他们太强了大佬们！！

其他方法可参考：https://leetcode.cn/problems/longest-consecutive-sequence/solution/xiao-bai-lang-ha-xi-ji-he-ha-xi-biao-don-j5a2/

并查集：这位看大佬https://leetcode.cn/problems/longest-consecutive-sequence/solution/by-lfool-jdy4/