3Sum (三數之和) 🟡 Medium¶

📌 LeetCode #15 — 題目連結 | NeetCode 解說

1. 🧐 Problem Dissection (釐清問題)¶

題目給我們一個整數陣列 nums，要求找出所有 Unique Triplets [nums[i], nums[j], nums[k]] 使得：

i != j, i != k, j != k (不同元素)
nums[i] + nums[j] + nums[k] == 0 (總和為 0)

回傳這些 triplets。注意：Output 不可以包含重複的 triplets。

Input: [-1,0,1,2,-1,-4]
Output: [[-1,-1,2], [-1,0,1]]
Constraints:
\(3 <= nums.length <= 3000\)
Space: 最好是 \(O(1)\) or \(O(n)\) (不含 output)。
Clarification:
"Unique triplets" 是最棘手的部分。例如 [-1, 0, 1] 和 [0, 1, -1] 視為同一個。

2. 🐢 Brute Force Approach (暴力解)¶

三層迴圈：

for i ...
  for j ...
    for k ...
      if nums[i] + nums[j] + nums[k] == 0 -> add to set (for dedup)

Time: \(O(n^3)\)。對於 \(n=3000\)， \(n^3 \approx 2.7 \times 10^{10}\)，絕對 TLE。

3. 💡 The "Aha!" Moment (優化)¶

這題其實是 Two Sum II 的延伸。

如果我们先**固定一個數字** nums[i]，那麼問題就變成了：在 nums[i+1...end] 中找出兩個數字，使得它們的和等於 -nums[i]。 -> 這就是 Two Sum！

為了有效利用 Two Sum II (Sorted Array + Two Pointers) 的高效能，並解決最麻煩的「去重 (De-duplication)」問題，我們可以：

Sort the Array: 讓所有數字由小到大排列。
- 這對去重至關重要：相同的數字會聚在一起。
Iterate i: 這是我們固定的第一個數字。
- 如果 nums[i] > 0，因為已排序，後面的數字肯定更大，總和不可能回頭變成 0，直接 break。
- 去重 (Skip Duplicates): 如果 nums[i] == nums[i-1]，跳過！這能避免產生重複的第一個數字。
Two Pointers (left, right): 尋找剩下的兩個數字。
- target = -nums[i]
- sum = nums[left] + nums[right]
- 如果 sum > target -> right--
- 如果 sum < target -> left++
- 如果 sum == target:
- 紀錄答案。
- left++, right--。
- Inner Loop 去重: Move left 後，如果 nums[left] == nums[left-1]，繼續 left++，直到找到新數字。這能避免產生重複的第二、三個數字。

🎬 Visualization (演算法視覺化)¶

⤢ 全螢幕開啟視覺化

4. 💻 Implementation (程式碼)¶

Approach: Sorting + Two Pointers¶

#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        // 1. Sort the array
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;

        for (int i = 0; i < nums.size(); i++) {
            // Optimization: if current number is positive, we can't make 0 sum with subsequent numbers
            if (nums[i] > 0) break;

            // Skip duplicate for the first number
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int left = i + 1;
            int right = nums.size() - 1;

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

                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    res.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;

                    // Skip duplicate for the second number
                    // 注意：只需負責一邊，另一邊會因為 sum 不平衡而自然移動
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;
                    }
                }
            }
        }
        return res;
    }
};

Python Reference¶

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        res = []
        nums.sort()

        for i, a in enumerate(nums):
            if a > 0:
                break

            if i > 0 and a == nums[i - 1]:
                continue

            l, r = i + 1, len(nums) - 1
            while l < r:
                threeSum = a + nums[l] + nums[r]
                if threeSum > 0:
                    r -= 1
                elif threeSum < 0:
                    l += 1
                else:
                    res.append([a, nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1
        return res

5. 📝 Detailed Code Comments (詳細註解)¶

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        // Step 1: 排序 (關鍵)
        // 為了使用 Two Pointers 並方便去重
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); i++) {
            // 剪枝優化：
            // 如果 nums[i] 已經 > 0，因為陣列已排序，後面不可能有負數來抵銷它
            if (nums[i] > 0) break;

            // 去重 (針對第一個數字 a)
            // i > 0 確保不檢查 nums[-1]
            if (i > 0 && nums[i] == nums[i-1]) continue;

            int low = i + 1;
            int high = nums.size() - 1;

            while (low < high) {
                int sum = nums[i] + nums[low] + nums[high];

                if (sum > 0) {
                    high--;
                } else if (sum < 0) {
                    low++;
                } else {
                    // 找到一組解
                    result.push_back({nums[i], nums[low], nums[high]});

                    // 找到了解之後，要繼續縮小範圍找下一組
                    low++;
                    high--;

                    // 去重 (針對第二個數字 b)
                    // 因為 c (第三個數字) 會被 sum 約束，所以只需對 b 去重即可
                    while (low < high && nums[low] == nums[low-1]) {
                        low++;
                    }
                }
            }
        }

        return result;
    }
};

6. 📊 Rigorous Complexity Analysis (複雜度分析)¶

Time Complexity: \(O(n^2)\)
Sorting: \(O(n \log n)\)。
Loops: 外層迴圈跑 \(n\) 次，內層 Two Pointers 跑 \(O(n)\) 次 -> 總共 \(O(n^2)\)。
總合: \(O(n^2)\)。這是比 Brute Force \(O(n^3)\) 巨大的進步。
Space Complexity: \(O(1)\) or \(O(n)\)
取決於 Sorting 演算法的實作細節 (C++ std::sort 混合使用 QuickSort/HeapSort/InsertionSort，通常視為 \(O(\log n)\) stack space)。
我們沒有使用額外的 Hash Map。

為什麼不用 Hash Map (Like Two Sum I)? 如果我們改用 Hash Map：

固定 i，然後用 Map 解 Two Sum。
優點：也可以做。
缺點：去重 (Dedup) 會非常非常痛苦。你需要在 Output 加入前檢查是否已存在，或者用 set<vector<int>> 來接結果然後再轉 vector，這會增加巨大的常數開銷。
在 3Sum 中，Sorted + Two Pointers 幾乎總是優於 Hash Map。

7. 💼 Interview Tips (面試技巧) ⭐ 高頻題¶

🎯 Follow-up 問題¶

面試官可能會問的延伸問題：

3Sum Closest? 4Sum?
如何處理重複解？

🚩 常見錯誤 (Red Flags)¶

避免這些會讓面試官扣分的錯誤：

⚠️ 沒有去重導致重複解
⚠️ 排序後忘記解的 indices 已改變

✨ 加分項 (Bonus Points)¶

這些會讓你脫穎而出：

💎 清晰的去重邏輯
💎 時間複雜度分析：O(n²)

站內相關¶

進階挑戰¶

3Sum Closest — LeetCode
4Sum — LeetCode