題目

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]
]

分析

ksum問題码泛，有O(n^(k-1))的解法粹懒。
本來想嘗試O(n^(k-2)log(n))的解法肥哎，但是失敗了颖变。果然前人都證明了還是有道理的，不過也讓我對這個問題的理解更加深刻了腮猖。
算法很簡單瘫辩，先排序肝匆，再枚舉k-2個數(shù)感昼，對于剩下的部分用兩個索引逼近剩余的值即可装哆。

實現(xiàn)

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

思考

代碼中的兩個do-while循環(huán)是為了防止重復結(jié)果而做的。
提交之后排名不高定嗓，所以我看了別人的做了些修改蜕琴。一是將i++之類的改成++i，據(jù)說這樣生成的匯編指令會少一點宵溅；二是去掉了push_back()函數(shù)中的vector<int>凌简，這個好像不需要，會自動轉(zhuǎn)換類型恃逻；最后是將這些數(shù)的和與要求的結(jié)果相等時作為單獨的情況雏搂，與大于和小于區(qū)分開來。然而寇损，在提交之后反而更慢了凸郑，讓我有點崩潰。題解中循環(huán)用的是迭代器润绵，也許這樣會快一點线椰，但是我懶得改了胞谈，下次注意吧尘盼。我修改過的代碼雖然慢吧，但是更美觀些烦绳，也在這邊貼一下吧卿捎。

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