最长连续序列

128. 最长连续序列

给定一个未排序的整数数组，找出最长连续序列的长度。

要求算法的时间复杂度为 O(n)。

示例:

输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

考虑枚举数组中的每一个数 x，考虑以其为起点，不断尝试匹配 x + 1，x + 2，…… 是否存在。采用暴力法，需要 O(n) 来遍历每个元素，使用 O(n^2) 来求取最长连续序列，时间复杂度 O(n^2)，总共时间复杂度O(n^3)。我们可以采用哈希表优化，这样判断一个数字是否存在只用 O(1)，总共时间复杂度O(n^2)。分析判断的过程，我们发现执行了很多不必要的枚举，如果已知有一个 x, x+1, x+2, … , x+y 的连续序列，我们从 x+1, x+2, … , x+y 等位置开始寻找的最长连续序列绝对小于从 x 处得到的最长连续序列长度大。因此，我们在外层循环的时候跳过这种情况。

如何跳过这种情况呢？由于我们要枚举的数 x 一定在数组中不存在前驱数 x - 1 的，不然我们会从 x - 1处开始尝试匹配，因此在哈希表中检查是否存在数 x - 1 即能判断是否需要跳过。

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> s = new HashSet<>();
        //生成哈希表
        for(int num : nums){
            s.add(num);
        }

        int longestStreak = 0;
        for(int num : nums){
            //判断是否跳过匹配
            if(!s.contains(num - 1)){
                int currentNum = num;
                int currentStreak = 1;
			//匹配
                while(s.contains(currentNum + 1)){
                    currentNum++ ;
                    currentStreak++ ;

                }
			//更新最大长度
                longestStreak = Math.max(currentStreak, longestStreak);
            }
        }
        return longestStreak;
    }
}

时间复杂度O(n) ，空间复杂度 O(n)。