LeetCode 128 Longest Consecutive Sequence：O(n) 哈希表 + 懶標記去重

題目描述

給定未排序整數數組，找出最長連續數字序列的長度（連續指數值連續，不要求數組中連續）。要求 O(n) 時間複雜度。

示例：[100, 4, 200, 1, 3, 2] → 最長序列 [1,2,3,4] 長度 4。

核心技巧：哈希表 + 「只從序列起點開始擴展」

若對每個數嘗試向左右擴展，會導致大量重複訪問（如 1,2,3,4 各自向右擴展共訪問 10 次）。關鍵優化：

1. 將所有數存入 unordered_set（或 unordered_map<int, bool> 標記是否已訪問）
2. 遍歷數組，對於當前數 x，只有當 x-1 不在集合中時，才以 x 為起點向右擴展（x+1, x+2, ...）
3. 擴展過程中將訪問過的數標記/移除，保證每個數最多被訪問一次

此法保證總訪問次數 ≤ 2n，時間複雜度 O(n)。

C++ 實現（標準庫版）

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

進階版：原地標記避免額外空間（面試常考）

若要求 O(1) 額外空間（修改輸入數組），可用 unordered_map 模擬「已訪問」標記：

class Solution {
public:
    int longestConsecutive(vector& num) {
        unordered_map visited;
        for (int x : num) visited[x] = false;
        
        int longest = 1;
        for (int x : num) {
            if (visited[x]) continue; // 已處理過的序列內部元素
            
            int len = 1;
            // 向右擴展
            int y = x + 1;
            while (visited.count(y)) {
                visited[y] = true;
                ++len; ++y;
            }
            // 向左擴展
            y = x - 1;
            while (visited.count(y)) {
                visited[y] = true;
                ++len; --y;
            }
            longest = max(longest, len);
        }
        return longest;
    }
};

關鍵點總結

複雜度分析

• 時間：O(n) — 每個數最多被查找 2 次（一次判斷是否為起點，一次在擴展中被訪問）
• 空間：O(n) — 哈希表存儲所有數

常見誤區

• ❌ 排序後掃描：O(n log n) 不滿足要求
• ❌ 對每個數雙向擴展不標記：最壞 O(n²)（如全連續數組）
• ✅ 正確：哈希表 + 起點判斷 + 單向擴展 + 標記

總結

本題是「線性時間處理無序數組連續性問題」的教科書級範例。核心思想：用空間換時間（哈希表），用「只處理起點」消除重複工作。此模式廣泛適用於：最長連續子數組、數組中缺失的最小正整數、環形數組連續序列等變體問題。