LeetCode 15. 3Sum 三數之和：雙指針夾逼去重完整解法

題目描述

給定包含 n 個整數的數組 nums，找出所有不重複的三元組 [a, b, c]，使得 a + b + c = 0。要求三元組內非遞減排序，解集不含重複三元組。

核心思路：排序 + 枚舉 + 雙指針

1. 排序：將數組升序排列，便於去重與雙指針移動
2. 枚舉第一個數：遍歷 i 從 0 到 n-3
3. 剪枝優化：
   • 若 nums[i] > 0 直接結束（三正數和不可能為 0）
   • 跳過重複的 nums[i]（i > 0 && nums[i] == nums[i-1]）
4. 雙指針夾逼：在 i+1 ... n-1 區間設置 l, r
   • sum > 0 → r--（和太大，需減小）
   • sum < 0 → l++（和太小，需增大）
   • sum == 0 → 記錄答案，l++ 並跳過重複 nums[l]

完整 C++ 代碼

class Solution {
public:
    vector> threeSum(vector& nums) {
        vector> res;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        
        for (int i = 0; i < n - 2 && nums[i] <= 0; ++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) {
                    --r;
                } else if (sum < 0) {
                    ++l;
                } else {
                    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;  // 繼續尋找下一組
                }
            }
        }
        return res;
    }
};

關鍵去重邏輯圖解

數組：[-4, -1, -1, 0, 1, 2]
i=0:  -4  → l=1(-1), r=5(2)  sum=-3 → l++
i=1:  -1  → l=2(-1), r=5(2)  sum=0  ✓  [-1,-1,2]
       跳過 l=2 重複 -1
i=2:  -1  (跳過，與 i=1 重複)
i=3:  0   → l=4(1), r=5(2)   sum=3  → r--

複雜度分析

• 時間：O(n²) —— 排序 O(n log n) + 雙層循環 O(n²)
• 空間：O(1) 或 O(log n)（排序棧空間），不計輸出空間

常見坑點

1. 去重位置錯誤：必須在找到有效三元組後跳過重複值，而非循環開始前
2. 邊界條件：l < r 而非 l <= r
3. 未處理 nums[i] > 0 提前終止，導致 TLE
4. 未使用 long long 防溢出（本題 int 範圍內安全）

擴展變體

• 3Sum Closest：記錄最接近 target 的 sum，無需去重
• 4Sum：雙層枚舉 + 雙指針，O(n³)
• 3Sum Smaller：計數滿足 sum < target 的三元組數