主題: 學習筆記

LeetCode 1：TypeScript Two Sum，用 Map 找出兩數索引

從兩層迴圈列舉配對，改用 Map 記錄先前值與索引，說明補數查詢、不變量與預期 O(n) 解法。

雙層迴圈會讓每個數字重新比較後面的元素。把走過的值和索引放進 Map 後，目前數字只要查詢它需要的補數，就能決定答案。

題目

對應原題：LeetCode 1：Two Sum

給定整數陣列 nums 與整數 target，找出兩個不同索引，使它們對應的值相加等於 target。題目保證恰有一組答案，索引順序不限。

暴力解會重複檢查配對

function twoSumBruteForce(nums: number[], target: number): number[] {
  for (let left = 0; left < nums.length; left += 1) {
    for (let right = left + 1; right < nums.length; right += 1) {
      if (nums[left] + nums[right] === target) {
        return [left, right];
      }
    }
  }

  throw new Error("No pair sums to target");
}

這個版本列出每一組不同索引，再比對和是否為 target。最壞情況會比較約 n(n - 1) / 2 組，因此時間複雜度是 O(n²)，額外空間是 O(1)。

用 Map 查補數

function twoSum(nums: number[], target: number): number[] {
  const indexByValue = new Map<number, number>();

  for (let index = 0; index < nums.length; index += 1) {
    const complementIndex = indexByValue.get(target - nums[index]);

    if (complementIndex !== undefined) {
      return [complementIndex, index];
    }

    indexByValue.set(nums[index], index);
  }

  throw new Error("No pair sums to target");
}

Map 的 key 是已走過的數值，value 是它的索引。處理 nums[index] 時，先查 target - nums[index] 是否已出現。若找到，該索引和目前索引就是答案；找不到才把目前數值存入 Map。

先查再存，才能保證不會把同一個元素拿來用兩次。get() 找不到 key 時回傳 undefined，所以用 !== undefined 判斷，不能寫成 if (complementIndex)。索引 0 是合法答案，但在 JavaScript 裡是 falsy。

為什麼這個掃描正確

每次處理索引 index 前，indexByValue 精確記錄所有小於 index 的元素及其索引。

若查到補數，補數索引必定早於目前索引，兩個索引不同，而且兩個值相加正好等於 target。若查不到，沒有任何先前元素能和目前值組成答案，因此把目前值存入 Map 不會漏掉答案。

任何合法答案都可寫成較早索引和較晚索引。掃描抵達較晚索引時，較早值已經存在於 Map，因此演算法必定回傳該組索引。

複雜度

暴力解是 O(n²) 時間、O(1) 額外空間。Map 解法在面試常用的平均雜湊查詢模型下，每次 get() 與 set() 都是預期 O(1)，總時間為預期 O(n)；Map 最多保存 n 個數值與索引，所以額外空間是 O(n)。

JavaScript 規格要求 Map 的平均存取時間低於線性，但不承諾固定的實作細節。面試回答應說「預期 O(n)」，不要把 Map 當成 O(1) 空間。MDN 的 Map 說明列出這個平均次線性的要求。

最小驗證

import assert from "node:assert/strict";

assert.deepStrictEqual(twoSum([2, 7, 11, 15], 9), [0, 1]);
assert.deepStrictEqual(twoSum([3, 2, 4], 6), [1, 2]);
assert.deepStrictEqual(twoSum([3, 3], 6), [0, 1]);

assert.deepStrictEqual() 直接驗證陣列內容，比只列出預期結果更可靠。Node.js 的 assert 文件說明深層嚴格比較的行為。

常見陷阱

• 先把目前值存進 Map，可能把同一個索引當成一對答案。
• 使用 if (map.get(complement))，在答案索引為 0 時誤判找不到。
• 把 Map 的儲存成本寫成 O(1)。它換來較快查詢，也需要 O(n) 額外空間。
• 先排序再用雙指標，卻忘了排序會改變原始索引。保留索引可以修正，但比直接使用 Map 多了不必要的步驟。

可遷移的思路

當題目在問「目前值是否能和先前資料組成條件」，可以先把條件改寫成要查詢的值。這題查補數，其他題目可能查已出現的值、累計次數或分組 key。Map 的 value 不一定是索引，也可以是次數、最早位置或其他後續計算需要的資料。

外部參考連結

• LeetCode 1：Two Sum：原始題目、範例與限制。
• MDN：Map：Map 的 key-value 語意、get()、set() 與平均存取要求。
• ECMAScript：Map Objects：JavaScript Map 的正式規格。
• Node.js：assert.deepStrictEqual()：陣列的深層嚴格比較。