主題: 學習筆記

LeetCode 15：TypeScript 3Sum，為什麼跳過重複值不會漏解

從全域 Set 的漏解問題，到排序與雙指標，再逐步說明 3Sum 的三個去重條件、正確性、複雜度與 assertions。

我一開始用三層迴圈找三個數，再用 Set 記錄已用過的索引。後來改成排序與雙指標，搜尋能跑了，但重複答案還沒處理好。最後的去重條件有 AI 輔助；這篇把原因拆開，並附上可自行執行的驗證程式，留作之後重新學習的紀錄。

題目

LeetCode 15：3Sum 要求找出總和為零的所有不重複三元組。每組必須使用三個不同索引，回傳數值而不是索引。輸出順序不限，陣列長度為 3 到 3000，元素介於 -100000 與 100000。

例如 [-1, 0, 1, 2, -1, -4] 的答案是 [[-1, -1, 2], [-1, 0, 1]]。

我的第一版為什麼會漏解

第一版找到答案後，會執行 set.add(i)、set.add(j)、set.add(k)，之後跳過這些索引。這等於把元素消耗掉了。

但 [-1, -1, 2] 和 [-1, 0, 1] 可以共用某個 -1 的索引。題目只禁止同一組裡重用索引，沒有禁止不同答案共用元素。全域 Set 因此會排除合法答案。

另一個問題是枚舉配對的順序。三層都從零開始，會把同一組索引的不同排列重複檢查。下面是補充的正確暴力解，讓 i < j < k，再以排序後的三個數作為去重 key。

function threeSumBruteForce(nums: number[]): number[][] {
    const unique = new Map<string, number[]>();
    for (let i = 0; i < nums.length - 2; i++) {
        for (let j = i + 1; j < nums.length - 1; j++) {
            for (let k = j + 1; k < nums.length; k++) {
                if (nums[i] + nums[j] + nums[k] !== 0) continue;
                const triplet = [nums[i], nums[j], nums[k]].sort((a, b) => a - b);
                unique.set(triplet.join(","), triplet);
            }
        }
    }
    return [...unique.values()];
}

這個版本不是我的最初程式，而是用來對照結果的參考實作。三層枚舉需要預期 O(n³) 時間，假設 Map 操作為預期常數時間；每次只排序三個數，成本不隨 n 成長。若有 m 組答案，Map 與輸出使用 O(m) 空間。

我最後整理的雙指標版本

以下保留最後提交的控制流程，只補上陣列型別與分號。排序和雙指標是在提示後寫出的，去重部分使用了 AI 提供的補正版。

function threeSum(nums: number[]): number[][] {
    const arr: number[][] = [];
    nums.sort((a, b) => a - b);
    for (let i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        let left = i + 1;
        let right = nums.length - 1;
        while (right > left) {
            const sum = nums[i] + nums[left] + nums[right];
            if (sum > 0) {
                right--;
            } else if (sum < 0) {
                left++;
            } else {
                arr.push([nums[i], nums[left], nums[right]]);
                right--;
                left++;
                while (left < right && nums[left] === nums[left - 1]) {
                    left++;
                }
                while (left < right && nums[right] === nums[right + 1]) {
                    right--;
                }
            }
        }
    }
    return arr;
}

先固定 nums[i]，就只剩尋找兩個數，使它們相加等於 -nums[i]。在已排序陣列裡，總和太小時移動左指標，總和太大時移動右指標。

以總和太小為例，右指標已是目前最右端。固定左端，任何更靠左的右端只會讓總和更小或相同，不可能變成零，因此能排除這個左端。總和太大的情況對稱。每次移動都排除一批確定無解的配對。

第一個判斷：固定數值只搜尋一次

if (i > 0 && nums[i] === nums[i - 1]) continue;

以 [-1, -1, 0, 1] 為例，固定第一個 -1 時已找到 [-1, 0, 1]。換成第二個 -1，目標仍然相同，而且後方可搜尋的元素只會更少，不會出現前一次無法找到的新數值組合。因此整輪可以跳過。

這不會排除 [-1, -1, 2]。第一次固定索引 0 的 -1 時，left 可以指向索引 1 的另一個 -1。兩個數值相同，但索引不同，完全合法。

i > 0 表示第一個元素沒有前一個元素可比較，不應跳過第一次搜尋。

後兩個判斷：答案記錄後才跳過相同值

考慮 [-2, 0, 0, 2, 2]，固定 -2：

先做了 left++，所以剛剛使用的左值位於 left - 1。nums[left] === nums[left - 1] 就是在問新左值是否仍和剛才一樣。若相同，繼續跳過整段重複值。

右端剛做完 right--，所以剛用過的右值在 right + 1。這就是右邊要比較下一格、左邊要比較前一格的原因。

固定第一個數 a 與第二個數 b 後，第三個數只能是 -a - b。已記錄 [a, b, c]，再使用另一個相同 b，只可能得到同一個 c，不會增加新的數值組合。相同 c 也適用這個理由。

這些去重發生在記錄答案之後。不要預先把陣列轉成 Set，否則 [-1, -1, 2] 和 [0, 0, 0] 所需的重複元素會消失。left < right 則確保繼續搜尋時仍有兩個不同位置。

為什麼不會漏解，也不會重複

固定 i 後，尚未排除的可行配對留在左右指標之間。總和太小或太大時，排序使我們能安全排除一端。等於零時，記錄答案，再排除只會產生相同數值組合的重複端點。

外層每種第一個數值只搜尋一次，內層每種符合目標的數值配對也只記錄一次。i < left < right 始終保證同一組使用不同索引。這三個性質一起滿足完整性、唯一性與索引限制。

複雜度與小幅整理

每個 i 的左右指標只往內移，搜尋至多線性次數；外層至多 n 輪，搜尋時間為 O(n²)。採常見的 O(n log n) 排序假設時，總時間仍為 O(n²)。

雙指標本身只用 O(1) 額外空間。若輸出有 m 組，需要 O(m)；排序的輔助空間依引擎實作而定，不能把整個函式直接說成常數空間。MDN sort 文件 也明確指出時間與空間複雜度沒有固定保證，且 sort 會修改原陣列。

原本的 i < nums.length 是正確的，最後兩輪不會進入 while。可改成 i < nums.length - 2 省掉空轉；也可在 nums[i] > 0 時提早結束，因為後面不會有負數。這些是補充整理，不改變核心複雜度，也不是去重正確的原因。

可執行驗證

將前面的兩個函式與以下測試放在同一個 TypeScript 檔執行。比較前只統一順序，不把結果轉成 Set，這樣多回傳一次相同答案仍會讓 assertion 失敗。

import assert from "node:assert/strict";

function canonical(groups: number[][]): string[] {
    return groups.map(group => [...group].sort((a, b) => a - b).join(",")).sort();
}

const cases: [number[], number[][]][] = [
    [[-1, 0, 1, 2, -1, -4], [[-1, -1, 2], [-1, 0, 1]]],
    [[0, 1, 1], []],
    [[0, 0, 0, 0], [[0, 0, 0]]],
    [[-1, -1, 0, 1], [[-1, 0, 1]]],
    [[-2, 0, 0, 2, 2], [[-2, 0, 2]]],
    [[-1, -1, 2], [[-1, -1, 2]]],
];

for (const [input, expected] of cases) {
    assert.deepEqual(canonical(threeSum([...input])), canonical(expected));
    assert.deepEqual(canonical(threeSumBruteForce(input)), canonical(expected));
}

其中 [-1, -1, 2] 確认去重沒有刪掉合法的相同數值，四個零驗證同一答案不會重複輸出。這些測試是文章補充的驗證內容。

重新學習時要解釋的事

下次空白重寫前，先說清楚「不同答案可以共用索引」，以及「相同第一個值為什麼不必重搜」。接著用 [-2, 0, 0, 2, 2] 說明 left 比前一格、right 比下一格的原因。能自己推導這些條件，再寫去重迴圈，比只記住三行判斷更有用。

外部參考連結

• LeetCode 15：3Sum
• MDN：Array.prototype.sort()
• Node.js：Strict assertion mode