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

問題描述

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

核心思路：哈希集合 + 只從序列起點開始擴展

1. 將所有數放入 unordered_set，O(1) 查找。
2. 遍歷數組，對每個 num，只有當 num-1 不在集合中時，才以 num 為起點向右擴展（num+1, num+2...）。
3. 記錄最大長度。

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

代碼實現

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> s(nums.begin(), nums.end());
        int best = 0;
        for (int x : s) {
            if (s.count(x - 1)) continue;  // 不是序列起點
            int y = x + 1;
            while (s.count(y)) ++y;
            best = max(best, y - x);
        }
        return best;
    }
};

原文代碼分析（供參考）

原文使用 map 模擬集合，並用偏移量處理負數。邏輯正確但 map 為紅黑樹，查找 O(log n)，總時間 O(n log n)，不符合 O(n) 要求。且偏移量 NUM=100 假設數據範圍，不具備通用性。推薦用 unordered_set。

複雜度

• 時間：O(n) 平均（unordered_set 操作攤還 O(1)）。
• 空間：O(n)。

關鍵點

1. 去重：集合自動去重，重複數字不影響結果。
2. 只從起點擴展：避免重複掃描同一序列。
3. 負數處理：unordered_set 原生支持負數，無需偏移。