题目链接

128. 最长连续序列

解题思路

先把数组中的所有数字放入哈希集合，既能去重，也能进行平均 O(1) 的存在性查询。

随后遍历集合。只有当 num - 1 不在集合中时，num 才可能是一段连续序列的起点。找到起点后不断检查 num + 1、num + 2，直到序列中断，并更新最长长度。

只从序列起点向后统计，避免从每个数字重复扫描同一段序列。

复杂度

  • 时间复杂度：平均 O(n)
  • 空间复杂度：O(n)

Java 解答

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums.length == 0) return 0;

        Set<Integer> num_set = new HashSet<Integer>();
        for (int num: nums) {
            num_set.add(num);
        }

        int longest_streak = 1;
        for (int num: num_set) {
            if (!num_set.contains(num - 1)) {
                int current_num = num;
                int current_streak = 1;

                while (num_set.contains(current_num + 1)) {
                    current_num += 1;
                    current_streak += 1;
                }
                
                longest_streak = Math.max(longest_streak, current_streak);
            }
        }
        return longest_streak;
    }
}

复盘

如果先排序，时间复杂度会达到 O(n log n)。哈希集合让存在性查询变快，而“只从起点出发”保证每个有效数字只会参与有限次扫描，从而达到平均线性复杂度。