主題: 學習筆記

LeetCode 217：TypeScript Contains Duplicate，用 Set 判斷重複值

比較整個 Set 的大小與陣列長度，或在一次掃描中提早找出重複值，說明 Set 解法的正確性與預期 O(n) 複雜度。

這題的重點不是排序，而是快速判斷某個值以前是否出現過。Set 只保留唯一值，很適合做這件事。

題目

對應原題：LeetCode 217：Contains Duplicate

給定整數陣列 nums。只要任一數值出現至少兩次就回傳 true；全部數值都不同時回傳 false。

直接比較 Set 大小

function containsDuplicate(nums: number[]): boolean {
  return new Set(nums).size !== nums.length;
}

這個版本正確。Set 不會保存重複值，所以只要 Set 的 size 小於原陣列長度，就表示至少有一個值被去重。

不過它仍會走完陣列並建立整個 Set。因此時間是預期 O(n)，額外空間也是 O(n)，不是 O(1)。建立 Set 時需要逐一處理輸入，最多也會保存 n 個不同值。

一次掃描，發現重複就結束

function containsDuplicate(nums: number[]): boolean {
  const seen = new Set<number>();

  for (const num of nums) {
    if (seen.has(num)) {
      return true;
    }

    seen.add(num);
  }

  return false;
}

這個版本的漸進複雜度相同，但遇到前段就重複的輸入時，可以立即回傳，不必走完整個陣列。面試時也比較容易從程式說明每一步的意義。

為什麼一次掃描正確

處理每個 num 前，seen 精確保存所有先前看過的不同數值。

若 seen.has(num) 為 true，代表 num 至少已在較早的位置出現一次，因此陣列含有重複值，可以回傳 true。若找不到，就把 num 加入 seen，讓這個條件在下一輪仍成立。

若迴圈完整結束都沒有命中，代表每個數字第一次出現時才被加入，沒有任何數值出現兩次，所以回傳 false 正確。

複雜度

兩個 Set 版本的最壞情況都是預期 O(n) 時間與 O(n) 額外空間。在面試常用的雜湊集合模型中，has() 和 add() 的單次操作是預期 O(1)。JavaScript 規格只要求平均存取時間低於線性，沒有承諾固定的底層實作。MDN 的 Set 文件有相同說明。

最小驗證

import assert from "node:assert/strict";

assert.equal(containsDuplicate([1, 2, 3]), false);
assert.equal(containsDuplicate([-1, -3, 1]), false);
assert.equal(containsDuplicate([1, 1, 1, 3, 3, 4, 3, 2, 4, 2]), true);
assert.equal(containsDuplicate([2]), false);

常見陷阱

• 把 new Set(nums) 當成 O(1)。它需要讀取所有輸入，並在最壞情況保存所有不同數字。
• 為了不用額外空間先排序。排序可行，但時間會變成 O(n log n)，而且若直接排序會改動輸入陣列。
• 在遇到重複值後仍繼續掃描。回傳型題目可以早點結束。
• 只列預期結果，卻沒有可執行的 assertion。可執行測試才能驗證輸出。

可遷移的思路

題目只問「是否看過」，優先想到 Set。如果還需要位置、次數或其他資料，再改用 Map。先辨認要保存的是存在性還是額外資訊，能避免一開始就選到比題目需要更重的資料結構。

外部參考連結

• LeetCode 217：Contains Duplicate：原始題目、範例與限制。
• MDN：Set：Set 的唯一值語意、has()、add() 與平均存取要求。
• ECMAScript：Set Objects：JavaScript Set 的正式規格。
• Node.js：assert.equal()：基本相等斷言。