主題: 學習筆記
TypeScript 最長連續序列：為什麼 Set 掃描不是 O(n²)
從排序解法進步到 Set 解法，推導只從序列起點展開的關鍵，並嚴謹說明最長連續序列的預期 O(n) 複雜度。
我一開始會想到「去重、排序、再掃描」，而且那個解法確實能得到正確答案；問題是題目要求預期 O(n)，排序已經讓它成為 O(n log n)。在 AI 輔助下改成 Set 後，我真正需要補上的不是另一段程式碼，而是：為什麼外層迴圈裡還有 while，總工作量卻不會變成 O(n²)？
題目
給定一組未排序整數，找出最長連續整數序列的長度。重複數字只算一次，不得使用排序，並以預期 O(n) 時間完成。
[100, 4, 200, 1, 3, 2, 2]
→ 4，因為最長序列是 [1, 2, 3, 4]排序版為什麼不符合限制
去重後排序，再比較相鄰數字，是正確而直觀的解法。掃描本身是 O(n)，但比較排序通常以 O(n log n) 分析，所以整體無法達到題目要求。
這個版本仍有學習價值：它先說清楚「連續」的判斷。但面試遇到明確的 O(n) 限制時，必須找到不靠全域排序的查找方式。
關鍵：只從序列起點往後走
先把所有數字放進 Set 去重。對每個 num，若 num - 1 也存在，num 就不是序列起點，直接略過。只有找不到前一個數字時，才從 num 開始向後尋找 num + 1、num + 2。
例如 {1, 2, 3, 4} 中，只有 1 會啟動 while。2、3、4 都因為存在前一個數字而跳過。若從每個數字都往後掃，則會分別走長度 4、3、2、1；在一條長序列上，總和會成為 O(n²)。
TypeScript 解法
function longestConsecutive(nums: readonly number[]): number {
const values = new Set(nums);
let longest = 0;
for (const num of values) {
if (values.has(num - 1)) continue;
let length = 1;
while (values.has(num + length)) {
length += 1;
}
longest = Math.max(longest, length);
}
return longest;
}為什麼所有 while 加起來仍是線性
不能只因為 length 持續增加，就宣稱每個數字只走一次。真正的理由是「只有序列起點能進入 while」。去重後的每個數字只屬於一條連續序列，而每條序列只會被它的最小值展開一次。
外層 for 查看每個唯一數字一次；所有內層 while 合計也只走過這些序列中的數字一次。因此，在 Set.has() 採常見的平均常數時間模型時，預期時間是 O(n)，額外空間是 O(n)。
語言規格並沒有要求 JavaScript Set 一定使用 hash table 或保證 O(1)。ECMAScript 要求平均存取時間必須次線性，實作也可以使用 tree。把這題說成預期 O(n)，是在面試常用的 hash-set 模型下分析，而不是對所有 engine 的最壞情況保證。
最小驗證
import assert from "node:assert/strict";
assert.strictEqual(longestConsecutive([100, 4, 200, 1, 3, 2, 2]), 4);
assert.strictEqual(longestConsecutive([0, -1, 1, 2, -2]), 5);
assert.strictEqual(longestConsecutive([]), 0);
assert.strictEqual(longestConsecutive([7, 7, 7]), 1);這些案例涵蓋重複值、負數、空陣列與只有一個唯一值。它們不需要測試框架，卻能在核心行為退化時直接失敗。
常見陷阱
- 使用排序，答案雖然正確，卻違反預期
O(n)的限制。 - 從每個數字都向後展開，長序列會退化成
O(n²)。 - 忘記先去重，重複值會干擾計數或造成重複工作。
- 看到巢狀迴圈就直接判定
O(n²)，沒有計算元素實際被內層迴圈處理幾次。 - 把
Set.has()的平均常數時間模型說成 ECMAScript 的硬性保證。
我學到什麼
- 題目限制常在提示需要哪種資料結構；禁止排序時，快速 membership lookup 是明顯方向。
- 巢狀迴圈不必然是平方時間，重點是所有內層迭代加總後的工作量。
num - 1的判斷不是小優化，而是避免重複展開同一序列的正確性與複雜度核心。- AI 提供的解法仍需要我能用 amortized analysis 自己解釋，才算真正理解。
外部參考連結
- MDN：Set：確認唯一值語意與規格要求的平均次線性存取。
- ECMAScript：Set Objects：查閱 JavaScript
Set的正式語意。 - Node.js：assert.strictEqual()：用最小 assertion 驗證回傳長度。