LeetCode Longest Consecutive Sequence——O(n) HashSet 掃描尋找最長連續序列

問題描述

給未排序整數數組，求最長連續整數序列的長度（序列中數字可不連續存放）。要求 O(n) 時間。

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

O(n) 解法：HashSet + 只從序列起點擴展

• 所有數存入 `HashSet`，O(1) 查找。
• 遍歷數組，對每個 `num`：
  • 若 `num-1` 不在集合中 → `num` 是某連續序列的起點。
  • 從 `num` 向上 `while(set.contains(cur)) cur++` 計算長度。
  • 更新最大長度。
• 每個數最多被訪問 2 次（一次作起點判斷，一次作序列內部擴展），總時間 O(n)。

代碼實現

class Solution {
    public int longestConsecutive(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        Set set = new HashSet<>();
        for (int x : nums) set.add(x);
        int res = 1;
        for (int x : nums) {
            if (!set.contains(x - 1)) { // 起點
                int cur = x, len = 1;
                while (set.contains(cur + 1)) {
                    ++cur; ++len;
                }
                res = max(res, len);
            }
        }
        return res;
    }
}

關鍵點

• 只從起點擴展：`!set.contains(x-1)` 保證每個序列只處理一次，避免重複掃描。
• HashSet O(1) 查找：支撐整體線性時間。
• 原地修改集合：擴展時可 `set.remove(cur)` 標記已處理，進一步減少外層循環判斷（但需遍歷副本或小心並發修改）。

複雜度

• 時間：O(n) 平均（HashSet 操作攤銷 O(1)）。
• 空間：O(n) 存儲集合。

總結

最長連續序列 O(n) 經典解法：HashSet 存所有數，只從序列起點（無前驅）向後擴展計算長度。避免了排序 O(n log n)，體現「以空間換時間 + 只處理起點」的巧妙優化。