最长连续序列（leetcode hot100)

力扣链接：最长连续序列

本题重点

降低时间复杂度为O（n)：当一个数是连续序列的第一个数的情况下才会进入内层循环，然后在内层循环中匹配连续序列中的数，因此数组中的每个数只会进入内层循环一次。

解题步骤：

1.创建一个HashSet，值的类型是int。

2. 遍历数组nums中的每一个数并存入set中（去重）。

3.遍历去重后的set，加上if条件（当一个数是连续序列的第一个数的情况下才会进入内层循环）

4.循环遍历求出当前最长连续序列

5.每次遍历更新最长连续序列的值

Java代码实现：

class Solution {
        public int longestConsecutive(int[] nums) {
            if (nums == null || nums.length == 0) return 0;
            HashSet<Integer> set = new HashSet<>();
            for (int i : nums) {
                set.add(i);
            }
            int maxStreak = 1;
            //这里遍历的是去重后的set
            for (int num : set) {
                int sum = 1;
                if (!set.contains(num - 1)) {
                    while (set.contains(num + 1)) {
                        num++;
                        sum++;
                    }
                    //更新最长连续序列的值
                    maxStreak = maxStreak > sum ? maxStreak : sum;
                }
            }
            return maxStreak;
        }
    }