題目描述

給定無序整數數組，求最長連續整數序列長度（元素可不連續存放）。要求 O(n) 時間複雜度。

示例： [100,4,200,1,3,2] → [1,2,3,4] 長度 4

核心洞察：Hash Set O(1) 查找

O(n) 提示用 Hash 容器而非 DP。思路：

1. 所有數入 unordered_set（去重 + O(1) 查找）
2. 遍歷數組，對每個數 num：
   • 若 num-1 不在集合中 → num 是序列起點
   • 從起點向上 num+1, num+2... 擴展，計算長度
   • 更新最大長度

關鍵優化：只從序列起點擴展，每個數最多被訪問 2 次（一次判斷是否起點，一次在擴展中），總體 O(n)。

完整代碼

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> all(nums.begin(), nums.end());
        unordered_set<int> visited;
        int maxLen = 0;
        for (int num : nums) {
            if (visited.count(num)) continue; // 已處理過
            if (all.count(num - 1)) continue; // 非起點，跳過
            // 從起點向上擴展
            int len = 0;
            int cur = num;
            while (all.count(cur)) {
                visited.insert(cur);
                len++;
                cur++;
            }
            maxLen = max(maxLen, len);
        }
        return maxLen;
    }
};

優化版（無需 visited 集合）

直接在 all 中擴展並刪除：

int longestConsecutive(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int maxLen = 0;
    for (int num : nums) {
        if (!s.count(num - 1)) { // 起點
            int cur = num, len = 0;
            while (s.count(cur)) {
                s.erase(cur); // 刪除避免重複訪問
                len++; cur++;
            }
            maxLen = max(maxLen, len);
        }
    }
    return maxLen;
}

複雜度分析

• 時間：O(n) 平均（unordered_set 查找/刪除 O(1) 平均）
• 空間：O(n) 存儲集合

注意： 最壞情況 Hash 衝突退化為 O(n²)，但極罕見。面試中可說明平均 O(n)。

常見誤區

• 以為 O(n) 必須用 DP → 實際 Hash 容器也可達到
• 用 set/map（紅黑樹）導致 O(n log n) → 必須用 unordered_set/unordered_map
• 重複擴展同一序列 → 起點判斷 + 刪除/標記訪問解決