1.题目

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

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

2.示例

输入：nums = [100,4,200,1,3,2]

输出：4

解释：最长数字连续序列是 [1, 2, 3, 4]。所以它的长度为 4。

3.个人解法

先利用Arrays对数组进行排序，然后遍历这个数组，判断 i 和 i+1 是否相差为1，若满足则让length++

这样的不足是：仅能通过最开头的连续序列，且无法保证是最长的连续序列

4.官方解法

基本思路：利用哈希表，先将数组放进哈希表setNums中，对哈希表进行遍历，枚举一个数x，若表中存在一个数的值为x+1，则让长度length++

优化点：再设置一个哈希表useNums，用于记录已经使用过的数x，可以达到去重的目的

class Solution {
    public int longestConsecutive(int[] nums) {
        //声明一个HashSet集合setNums，用来存储数组中的元素 —— 为了便于查找
        Set<Integer> setNums = new HashSet<>();
        for (int num : nums) {
            setNums.add(num);
        }
        //声明一个变量，用来存储最长的连续序列的长度
        int longest = 0;
        //声明一个HashSet集合，用来存储已经被使用过的元素 —— 为了避免重复查找
        Set<Integer> useNums = new HashSet<>();
        //遍历setNums集合，查找每一个元素是否是连续的
        for(Integer setNum : setNums){
            //如果当前元素已经被使用过，则跳过
            if(useNums.contains(setNum)){
                continue;
            }
            //取出setNums中的一个元素，看它是否是连续的
            int nextNum = setNum + 1;
            int currentLength = 1;
            //如果下一个元素也在setNums集合中，那么长度就应该加1
            while(setNums.contains(nextNum)){
                //使用过了，添加到useNums集合中
                useNums.add(nextNum);
                currentLength++;
                nextNum++;
            }
            //避免数组长度为0的情况
            longest = Math.max(longest, currentLength);
        }

        return longest;
    }
}