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

LeetCode 128. Longest Consecutive Sequence 題目與解法

給定未排序整數數組，求最長連續數字序列的長度（非子數組，而是集合中連續的整數）。要求 O(n) 時間複雜度。例如 [100,4,200,1,3,2] → 最長連續序列 [1,2,3,4]，長度 4。

核心思想：只從序列起點開始擴展

將所有數存入 unordered_set。遍歷數組，對每個數 num，若 num-1 不在集合中，則 num 是某個連續序列的起點。從 num 開始向上查找 num+1, num+2... 直到不存在，記錄長度。這樣每個數最多被訪問兩次（一次判斷是否為起點，一次在擴展時被訪問），總時間 O(n)。

代碼實現

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

關鍵點解析

• 使用 unordered_set 實現 O(1) 平均查找。
• 只從「無前驅」的數字開始擴展，避免重複計算。
• 空間 O(n)，滿足題目要求。

常見誤區

若對每個數都向兩邊擴展並標記已訪問（如原文代碼用 b 集合），雖然也能 AC，但邏輯較繁瑣。上述「只找起點」寫法更簡潔、常數更小，是標準解法。