LeetCode 15 3Sum：三數之和為零

題目描述

給定整數陣列 S，找出所有不重複三元組 a,b,c 使 a+b+c=0。三元組需非遞減序，結果無重複。

例：S = [-1,0,1,2,-1,-4] → [[-1,0,1], [-1,-1,2]]。

雙指針標準解法

1. 排序陣列。
2. 固定第一個數 current（current < len-2 && nums[current] <= 0）。
3. 左右指針 front, back 夾逼求和。
4. 去重：三層 do-while 跳過相同值。

C++ 實現

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> res;
        int len = nums.size();
        for (int cur = 0; cur < len - 2 && nums[cur] <= 0; ++cur) {
            int front = cur + 1, back = len - 1;
            while (front < back) {
                int sum = nums[cur] + nums[front] + nums[back];
                if (sum < 0) ++front;
                else if (sum > 0) --back;
                else {
                    res.push_back({nums[cur], nums[front], nums[back]});
                    do ++front; while (front < back && nums[front-1] == nums[front]);
                    do --back; while (front < back && nums[back+1] == nums[back]);
                }
            }
            while (cur < len - 2 && nums[cur+1] == nums[cur]) ++cur;
        }
        return res;
    }
};

相關題目

• LeetCode 16 3Sum Closest：最接近目標值三數和。
• LeetCode 18 4Sum：四數之和。