0128-Longest-Consecutive-Sequence

Problem Description

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

You must write an algorithm that runs in O(n) time.

A Longest Consecutive Sequence is the longest chain of numbers in a given dataset (like an array or tree) where each number is exactly one integer greater than the previous one.

Solution

目標是在 O(n) 內找出最長的「連續整數」串。先把數字放進 hash 容器、用 O(1) 查詢「某個數在不在」，是兩種解法共同的基礎。

方法一：Hash Set — O(n) 標準解

把所有數丟進 unordered_set，然後只從序列起點往上數。所謂起點，就是 n - 1 不在集合裡的數。

// Time: O(n)
// Space: O(n)
class Solution {
 public:
  int longestConsecutive(vector<int>& nums) {
    unordered_set<int> s(nums.begin(), nums.end());
    int ans = 0;
    for (int n : s) {
      if (s.count(n - 1)) continue;   // 不是序列起點就跳過
      int cur = n, len = 1;
      while (s.count(cur + 1)) {       // 從起點往上數
        ++cur;
        ++len;
      }
      ans = max(ans, len);
    }
    return ans;
  }
};

方法二：Union-Find — 把相鄰數字併進同一集合

換個角度：把每個數字當節點，相鄰（差 1）的數字 union 在一起，最後最大的 component 大小就是答案。因為元素是任意整數（可能為負或很大），parent／size 用 unordered_map 而非陣列。

// Time: O(n·α(n))（路徑壓縮 + union by size，近似 O(n)）
// Space: O(n)
struct UnionFind {
  unordered_map<int, int> parent, size;

  void add(int x) {
    if (parent.count(x)) return;            // 防重複數字重設結構
    parent[x] = x;
    size[x] = 1;
  }
  int find(int x) {
    if (parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }
  void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;
    if (size[px] > size[py]) swap(px, py);  // union by size（可選，掛小到大）
    parent[px] = py;
    size[py] += size[px];
  }
};

class Solution {
 public:
  int longestConsecutive(vector<int>& nums) {
    UnionFind uf;
    for (int n : nums) uf.add(n);                       // 1. 先把所有數加入
    for (int n : nums) {
      if (uf.parent.count(n - 1)) uf.unite(n, n - 1);   // 2. 只 union 存在的鄰居
      if (uf.parent.count(n + 1)) uf.unite(n, n + 1);
    }
    int ans = 0;
    for (auto& [k, sz] : uf.size) ans = max(ans, sz);
    return ans;
  }
};

兩個重點：

• 為什麼拆兩個迴圈：先把所有數 add 進結構，再逐一檢查 n-1／n+1 是否存在、存在才 unite。這樣連邊前保證元素都已存在，不必去推理陣列順序（單迴圈 + 守衛其實也對，較晚處理的那個會反向接上，只是要多想一層）。
• size 一身兼二職：既是 union by size 的依據，也是 component 大小（即答案）。size[py] += size[px] 在有沒有那行 swap 的情況下都會在根節點正確累加；拿掉 swap 仍正確，只是退化到約 O(n log n)。

Related Problems

0217-Contains-Duplicate — 同樣以 unordered_set 為核心的查詢／去重
0200-Number-of-Islands — Union-Find 連通分量的經典應用
0684-Redundant-Connection — 直接練 Union-Find 的 find／unite 與環偵測