LeetCode Longest Consecutive Sequence - O(n) 哈希表解法詳解

給定未排序整數數組，找出最長連續序列的長度，要求 O(n) 時間複雜度。例如 [100, 4, 200, 1, 3, 2] 最長連續序列為 [1,2,3,4]，長度 4。

核心技巧：哈希表去重與單向擴展

1. O(1) 查找：使用 unordered_set 或 unordered_map 存儲所有數字，支持常數時間存在性判斷。
2. 只從序列起點開始擴展：對於數字 x，若 x-1 存在於集合中，則 x 必不在最長序列的起點，跳過它。只有當 x-1 不存在時，x 才可能是某個連續序列的起點，然後向右擴展（x+1, x+2...）計算長度。

這樣每個元素最多被訪問兩次（一次判斷是否為起點，一次在擴展中被訪問），總時間 O(n)。

算法流程

1. 將所有數字放入 unordered_set numSet。
2. 遍歷數組，對於每個 num：
   • 若 numSet.count(num - 1) 為真，繼續下一個。
   • 否則，從 current = num 開始，while numSet.count(current + 1)，current++，累計長度。
   • 更新最大長度。

代碼實現 (C++)

class Solution {
public:
    int longestConsecutive(vector& nums) {
        unordered_set numSet(nums.begin(), nums.end());
        int longest = 0;
        for (int num : nums) {
            // 只有當 num 是序列起點時才擴展
            if (numSet.count(num - 1)) continue;
            int current = num;
            int streak = 1;
            while (numSet.count(current + 1)) {
                current++;
                streak++;
            }
            longest = max(longest, streak);
        }
        return longest;
    }
};

總結

這道題展示了哈希表在「以空間換時間」和「避免重複計算」上的威力。關鍵點在於「只從序列起點開始擴展」，將原本可能 O(n^2) 的暴力擴展優化為 O(n)。這是解決「連續序列/子數組」類問題的常用套路。