LeetCode 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)

解題思路分析

這是一個經典的三數之和問題。最直觀的暴力解法需要三層循環，時間複雜度為 O(n³)，對於大數據會超時。優化的核心思路是：

1. 先排序：將數組排序，便於後續去重和雙指針操作
2. 固定一個數，雙指針查找另外兩個數：固定第一個數 a，問題轉化為在剩餘數組中找兩數之和為 -a
3. 去重策略：利用排序後相同元素相鄰的特性，跳過重複元素

詳細算法步驟

1. 對數組進行升序排序
2. 遍歷數組，對於每個位置 i 的元素 num[i] 作為第一個數：
   • 若 i > 0 且 num[i] == num[i-1]，跳過（避免重複三元組）
   • 設定目標值 target = -num[i]
   • 在 i+1 到末尾的子數組中，使用雙指針 left 和 right 查找兩數之和等於 target
3. 雙指針查找過程：
   • 計算當前和 curSum = num[left] + num[right]
   • 若 curSum == target：找到有效三元組，加入結果集，並移動指針同時跳過重複元素
   • 若 curSum < target：left++（需要增大和）
   • 若 curSum > target：right--（需要減小和）

代碼實現 (C++)

/*********************************
 * 日期：2014-01-18
 * 作者：SJF0115
 * 題號: 3Sum
 * 來源：https://oj.leetcode.com/problems/3sum/
 * 結果：AC
 **********************************/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>> triplets;
        int len = num.size();
        if (len < 3) return triplets;
        
        // 排序
        sort(num.begin(), num.end());
        
        for (int i = 0; i < len - 2; i++) {
            // 跳過重複元素
            if (i != 0 && num[i] == num[i-1]) continue;
            
            int target = -num[i];
            int left = i + 1;
            int right = len - 1;
            
            while (left < right) {
                int curSum = num[left] + num[right];
                
                if (target == curSum) {
                    // 找到有效三元組
                    triplets.push_back({num[i], num[left], num[right]});
                    
                    // 跳過重複元素
                    while (left < right && num[left] == num[left + 1]) left++;
                    while (left < right && num[right] == num[right - 1]) right--;
                    
                    left++;
                    right--;
                } else if (target > curSum) {
                    // 和太小，左指針右移
                    while (left < right && num[left] == num[left + 1]) left++;
                    left++;
                } else {
                    // 和太大，右指針左移
                    while (left < right && num[right] == num[right - 1]) right--;
                    right--;
                }
            }
        }
        return triplets;
    }
};

int main() {
    vector<int> vec = {-2, 0, 0, 2, 2};
    Solution solution;
    vector<vector<int>> result = solution.threeSum(vec);
    
    for (const auto& triplet : result) {
        for (int val : triplet) {
            printf("%d ", val);
        }
        printf("\n");
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(n²) — 排序 O(n log n)，雙層循環 O(n²)
• 空間複雜度：O(1) 或 O(n) — 視排序算法而定，不計輸出空間

測試用例

輸入：[-2, 0, 0, 2, 2]
預期輸出：[[-2, 0, 2]]

關鍵點總結

• 排序是去重和雙指針法的前提
• 固定第一個數後，子問題退化為 Two Sum II
• 三處去重：外層循環、雙指針找到解後、雙指針移動時
• 注意邊界條件：數組長度小於 3 直接返回空