LeetCode 15: 三數之和 (3Sum) 完整解析與優化策略

給定一個包含 n 個整數的數組 S，判斷是否存在三個元素 a, b, c 使得 a + b + c = 0？找出所有滿足條件且不重複的三元組。

題目要求

• 三元組 (a, b, c) 必須按非遞減順序排列（即 a ≤ b ≤ c）
• 解集不能包含重複的三元組

範例

輸入：S = [-1, 0, 1, 2, -1, -4]

輸出：[[-1, 0, 1], [-1, -1, 2]]

核心思路：排序 + 雙指針

這道題可以轉化為「兩數之和」的變體。關鍵在於處理重複元素——若不加剪枝，LeetCode 會判定超時（TLE）。

1. 先排序：時間複雜度 O(N log N)。
2. 固定第一個指針：從頭遍歷到倒數第三個元素。
3. 雙指針查找：第二、三個指針分別從第一個指針的下一位和數組末尾向中間收斂，類似「兩數之和」。此步驟時間複雜度 O(N²)，總複雜度 O(N²)。
4. 必須剪枝：跳過相同元素以避免重複三元組，同時大幅減少無效計算。

關鍵剪枝細節

• 外層循環：若 nums[i] == nums[i-1] 則 continue。
• 內層雙指針：找到有效三元組後，移動左指針時跳過相同值；同理移動右指針。

參考代碼（C++）

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        if (n < 3) return res;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 2; ++i) {
            if (i > 0 && nums[i] == nums[i-1]) continue; // 剪枝
            int l = i + 1, r = n - 1;
            while (l < r) {
                int sum = nums[i] + nums[l] + nums[r];
                if (sum == 0) {
                    res.push_back({nums[i], nums[l], nums[r]});
                    while (l < r && nums[l] == nums[l+1]) ++l;
                    while (l < r && nums[r] == nums[r-1]) --r;
                    ++l; --r;
                } else if (sum < 0) ++l;
                else --r;
            }
        }
        return res;
    }
};

運行結果

Runtime: 68 ms，通過所有測試用例。