LeetCode Longest Consecutive Sequence & First Missing Positive：集合去重 + 線性掃描

問題一：Longest Consecutive Sequence (最長連續序列)

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

核心思路：HashSet + 只從序列起點開始擴展

1. 所有數存入 unordered_set (O(1) 查找)。
2. 遍歷數組，對每個 num，若 num-1 **不在**集合中，說明 num 是某連續序列的**起點**。
3. 從 num 向上連續查找 num+1, num+2... 計算長度。
4. 每個數最多被訪問 2 次 (一次判斷是否起點，一次在序列中被擴展)，總時間 O(n)。

關鍵代碼 (C++)

int longestConsecutive(vector& nums) {
    unordered_set s(nums.begin(), nums.end());
    int maxLen = 0;
    for (int x : nums) {
        if (s.count(x-1)) continue; // 非起點，跳過
        int len = 1;
        while (s.count(++x)) len++;
        maxLen = max(maxLen, len);
    }
    return maxLen;
}

問題二：First Missing Positive (缺失的第一個正數)

給定無序整數數組，找最小的缺失正整數。要求 O(n) 時間、O(1) 額外空間 (可修改數組)。

核心思路：原地哈希 (桶排序思想)

將數組視為哈希表：值 v 應放在索引 v-1 位置。遍歷數組，將每個 1≤v≤n 的數交換到正確位置。最後掃描，第一個 nums[i] != i+1 的位置即答案。

關鍵代碼 (C++)

int firstMissingPositive(vector& nums) {
    int n = nums.size();
    for (int i=0; i= 1 && nums[i] <= n && nums[i] != nums[nums[i]-1])
            swap(nums[i], nums[nums[i]-1]);
    }
    for (int i=0; i

複雜度對比


問題
時間
空間
關鍵技巧


Longest Consecutive
O(n)
O(n)
HashSet 只從起點擴展
First Missing Positive
O(n)
O(1)
原地哈希/桶排序



總結
兩道題都是「線性時間處理無序數組」的經典。Longest Consecutive 用「集合 + 起點判斷」避免重複掃描；First Missing Positive 用「原地哈希」將數組自身作為存儲結構，達到 O(1) 空間。掌握這兩種模式，可解決大多數「無序數組查找特定模式」問題。