15. 3Sum（三數之和）

題目描述

給定一個整數陣列 nums，找出所有不重複的三元組 [nums[i], nums[j], nums[k]]，使得 nums[i] + nums[j] + nums[k] === 0。

原題連結：LeetCode #15 - 3Sum

解題思路

暴力解：三重迴圈 — O(n³)

最直覺但效率最差，實際上會 TLE（Time Limit Exceeded）。

最佳解：排序 + 雙指針 — O(n²)

1. 先排序 nums，讓重複的數字相鄰，方便後續去重
2. 固定一個數 nums[i]（外層迴圈）
3. 在 i+1 到末尾的範圍內使用雙指針 left、right 尋找另外兩個數
4. 若三數之和 < 0，left++；若 > 0，right--；若 === 0，記錄並同時移動兩個指針，跳過重複值

去重關鍵：

• 外層：若 nums[i] === nums[i-1]，跳過
• 內層：找到答案後，跳過連續相同的 nums[left] 和 nums[right]

| | 時間複雜度 | 空間複雜度 | | ------------- | ---------- | ---------- | | 暴力解 | O(n³) | O(1) | | 排序 + 雙指針 | O(n²) | O(1) |

TypeScript 實作

function threeSum(nums: number[]): number[][] {
  const result: number[][] = [];
  nums.sort((a, b) => a - b); // 先排序

  for (let i = 0; i < nums.length - 2; i++) {
    // 去重：跳過外層重複值
    if (i > 0 && nums[i] === nums[i - 1]) continue;
    // 優化：最小的三個數之和已大於 0，後面不可能有解
    if (nums[i] > 0) break;

    let left = i + 1;
    let right = nums.length - 1;

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];

      if (sum === 0) {
        result.push([nums[i], nums[left], nums[right]]);
        // 去重：跳過內層重複值
        while (left < right && nums[left] === nums[left + 1]) left++;
        while (left < right && nums[right] === nums[right - 1]) right--;
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }

  return result;
}

執行步驟範例

以 nums = [-1, 0, 1, 2, -1, -4] 為例，排序後：[-4, -1, -1, 0, 1, 2]

| i | nums[i] | left | right | sum | 動作 | | --- | ------- | ---- | ----- | ------------ | ----------------------- | | 0 | -4 | 1 | 5 | -4+(-1)+2=-3 | left++ | | 0 | -4 | 2 | 5 | -4+(-1)+2=-3 | left++ (跳過重複) | | 0 | -4 | 3 | 5 | -4+0+2=-2 | left++ | | 0 | -4 | 4 | 5 | -4+1+2=-1 | left++ | | 1 | -1 | 2 | 5 | -1+(-1)+2=0 | ✓ 記錄 [-1,-1,2] | | 1 | -1 | 3 | 4 | -1+0+1=0 | ✓ 記錄 [-1,0,1] | | 2 | -1 | — | — | — | 跳過（與 nums[1] 重複） |

結果：[[-1,-1,2], [-1,0,1]]