128. Longest Consecutive Sequence

// 演算法：把所有數字放入雜湊集合，只從「沒有前一個數 (x-1)」的起點開始往上數，
// 累計每段連續序列的長度，取最大值。整體 O(n)。
// Algorithm: put all numbers in a hash set, then from each "start" (a value whose
// x-1 is absent) walk upward counting the run length; track the maximum. Overall O(n).

#include <stdlib.h>   // 提供 malloc / free / qsort 等 / provides malloc, free, etc.

// 為了在 C 裡有一個 O(1) 的「集合」，我們用開放定址雜湊表自己實作。
// To get an O(1) "set" in C, we build an open-addressing hash table ourselves.

#define EMPTY_SLOT 0x80000000  // 用一個不可能的整數標記空格 (此值超出題目範圍)
                               // A sentinel marking an empty slot (outside the input range).

// 把任意整數映射到表格索引 / map any integer to a table index.
static int hashIndex(long long key, int cap) {
    // key 可能是負數，先加上 cap 再取餘數，確保結果非負 / handle negatives: result stays in [0, cap).
    long long h = key % cap;
    if (h < 0) h += cap;
    return (int)h;
}

int longestConsecutive(int* nums, int numsSize) {
    if (numsSize == 0) return 0;  // 空陣列直接回傳 0 / empty input → 0.

    // 容量取 2 倍以上以降低碰撞；+1 避免容量為 0 / size table > 2x to keep collisions low.
    int cap = numsSize * 2 + 1;

    // 配置表格，每格存一個 int。malloc 回傳一塊未初始化記憶體的指標。
    // Allocate the table, one int per slot. malloc returns a pointer to raw memory.
    int* table = (int*)malloc(sizeof(int) * cap);

    // 把每一格初始化為 EMPTY_SLOT，表示目前是空的 / mark every slot empty first.
    for (int i = 0; i < cap; i++) table[i] = EMPTY_SLOT;

    // ---- 插入階段：把所有數字放進雜湊表，自動忽略重複 ----
    // ---- Insert phase: put every number into the table (duplicates harmlessly overwrite). ----
    for (int i = 0; i < numsSize; i++) {
        int v = nums[i];                 // 目前要插入的值 / the value to insert.
        int idx = hashIndex(v, cap);     // 算出它的起始格 / its starting slot.
        // 線性探測：若該格被別的值佔用，就往後一格找空位 (開放定址法)。
        // Linear probing: if the slot is taken by a different value, step to the next slot.
        while (table[idx] != EMPTY_SLOT && table[idx] != v) {
            idx = (idx + 1) % cap;       // % cap 讓索引繞回開頭 / wrap around to the front.
        }
        table[idx] = v;                  // 寫入值 (若已存在則原地覆寫，等於去重) / store (dups overwrite).
    }

    // ---- 查詢函式的內嵌寫法：用 lambda 在 C 不行，所以直接展開為一段探測迴圈 ----
    // In C there are no closures, so we inline the "contains" search where needed below.

    int longest = 1;  // 至少有一個元素，所以最短答案是 1 / at least one element exists → min 1.

    // ---- 主迴圈：對每個數字判斷它是不是序列起點 ----
    // ---- Main loop: for each number decide whether it starts a run. ----
    for (int i = 0; i < numsSize; i++) {
        int x = nums[i];

        // 檢查 x-1 是否存在：若存在，x 就不是起點，跳過以避免重複計算。
        // Check whether x-1 exists; if so, x is not a start, so skip (avoids redundant walks).
        long long prev = (long long)x - 1;   // 用 long long 防止 x = -2^31 時減 1 溢位 / avoid underflow.
        int pidx = hashIndex(prev, cap);
        int prevExists = 0;
        while (table[pidx] != EMPTY_SLOT) {  // 探測直到遇到空格才確定不存在 / probe until an empty slot.
            if (table[pidx] == (int)prev) { prevExists = 1; break; }
            pidx = (pidx + 1) % cap;
        }
        if (prevExists) continue;            // x-1 在 → x 不是起點 / x-1 present → not a start.

        // 到這裡 x 是某段序列的起點，開始往上數 x+1, x+2, ...
        // x is a run start: walk upward counting x+1, x+2, ...
        int curNum = x;       // 目前數到的數字 / the number we have reached.
        int curLen = 1;       // 這段的長度，從 1 起算 / current run length, starting at 1.

        while (1) {           // 無限迴圈，內部用 break 跳出 / loop until next number is absent.
            long long next = (long long)curNum + 1;  // 下一個要找的數 / the next value to look for.
            int nidx = hashIndex(next, cap);
            int found = 0;
            while (table[nidx] != EMPTY_SLOT) {       // 在表中搜尋 next / search for next in the table.
                if (table[nidx] == (int)next) { found = 1; break; }
                nidx = (nidx + 1) % cap;
            }
            if (!found) break;                        // 找不到下一個 → 這段結束 / chain ends.
            curNum = (int)next;                       // 接上，往上移動 / extend the chain.
            curLen++;                                 // 長度加一 / length grows by one.
        }

        if (curLen > longest) longest = curLen;       // 更新最長紀錄 / update the maximum.
    }

    free(table);   // 釋放 malloc 配置的記憶體，避免記憶體洩漏 / free the table to avoid a memory leak.
    return longest;
}

// 演算法：把所有數字放進 unordered_set (雜湊集合)，只從「x-1 不存在」的起點往上數，
// 累計每段連續序列長度並取最大。整體 O(n)。
// Algorithm: load all numbers into an unordered_set, walk upward only from run-starts
// (values whose x-1 is absent), track the longest run. Overall O(n).

#include <vector>          // std::vector 動態陣列 / dynamic array.
#include <unordered_set>   // std::unordered_set 雜湊集合，O(1) 平均查詢 / hash set, O(1) average lookup.
#include <algorithm>       // std::max 取較大值 / for std::max.
using namespace std;

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        // 用 nums 的頭尾迭代器一次建好集合；重複值會自動被忽略。
        // Build the set directly from nums's begin/end iterators; duplicates are dropped automatically.
        unordered_set<int> s(nums.begin(), nums.end());

        int longest = 0;  // 答案；空陣列時保持 0 / answer; stays 0 for empty input.

        // range-for：依序取出集合中每個元素 x (此處用 const 參考避免複製)。
        // range-for: iterate over each element x in the set (const reference avoids copying).
        for (const int x : s) {
            // s.count(x-1) 回傳 0 或 1，代表 x-1 在不在集合裡。
            // s.count(x-1) returns 0 or 1: whether x-1 is present.
            // 若 x-1 存在，x 不是起點，跳過 / if x-1 exists, x is not a start, skip.
            if (s.count(x - 1)) continue;

            // x 是序列起點，開始往上數 / x starts a run; walk upward.
            int curNum = x;     // 目前到達的數字 / current value reached.
            int curLen = 1;     // 本段長度 / current run length.

            // 只要下一個數還在集合裡就繼續延伸 / keep extending while the next value exists.
            while (s.count(curNum + 1)) {
                curNum++;       // 移到下一個連續數 / move to the next consecutive number.
                curLen++;       // 長度加一 / grow the length.
            }

            longest = max(longest, curLen);  // 更新最長紀錄 / keep the maximum.
        }

        return longest;
    }
};