題目描述

原題鏈接：3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

解題思路

跟2Sum一樣，先排一遍序，時(shí)間復(fù)雜度就至少是O(n lgn )了。
現(xiàn)在我要使 a+b+c = 0 ，我可以遍歷一遍排序后的數(shù)組，對(duì)每一個(gè)nums[i]，假設(shè)這里 a < b < c ，且 a = nums[i] ，也就是說(shuō)要找出 b + c = 0 - a 。

那么b和c在哪里？因?yàn)閿?shù)組是遞增的，所以b和c肯定在nums[i] （也就是a）的右邊。（因?yàn)橐呀?jīng)假設(shè) a 最小）那么對(duì)于數(shù)組中nums[i]右邊的部分，可以采用雙指針的思想，一個(gè)指針在最左邊，一個(gè)指針在最右邊，看看 b + c 是否等于 0 - a ，如果大了，那么右指針左移，如果小了，那么左指針右移，如果相等，則得到一個(gè)解。

還有一個(gè)重要的問(wèn)題就是解的去重，因?yàn)槲覀円?guī)定了 a < b < c，所以只要保證所有解中 a和b不都相同就可以了。舉個(gè)例子：

假如解集中已經(jīng)有 { [ -3, 1, 2 ] , [ -4, 2, 2] }
代碼還在跑，當(dāng)遇到 a = -3 且 b = 1的情況就自動(dòng)略過(guò)。因?yàn)閿?shù)組是遞增的，我只要檢查跟前一個(gè)元素是否相等即可。

代碼

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int> > result;
        
        if (nums.size() < 3)
            return result;
        for (int i = 0; i < nums.size() - 2; i ++){
            int a = nums[i];
            if (i > 0 && a == nums[i-1])
                continue;
            int bcSum = 0 - a;
            int bIndex = i + 1;
            int cIndex = nums.size() - 1;
            while (bIndex < cIndex){
                if (bIndex > i + 1 && nums[bIndex] == nums[bIndex - 1]) {
                    bIndex ++;
                    continue;
                }
                int b = nums[bIndex];
                int c = nums[cIndex];
                if (b + c > bcSum){
                    cIndex --;
                    continue;
                } else if (b + c < bcSum){
                    bIndex ++;
                    continue;
                } else {
                    result.push_back({a, b, c});
                    cIndex --;
                    bIndex ++;
                }
            }
        }
        
        return result;
    }
};