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:

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
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)

---

1. 排序
2. 夹逼定理

3. 避免重复

    class Solution {
    public:
        vector<vector<int>> threeSum(vector<int>& nums) {
            vector<vector<int>> res;
            if(!nums.size()){
                return res;
            }
            sort(nums.begin(), nums.end());
            auto begin = nums.begin();
            auto last = nums.end();
            for(auto i=begin; i<prev(last,2) && *i<=0; i++){
                if(i!=begin && *i==*(i-1)){
                    continue;
                }
                auto j=i+1;
                auto k=last-1;
                while(j<k){
                    auto t = *i+*j+*k;
                    if(t==0){
                        res.push_back({*i,*j,*k});
                        j++;
                        k--;
                        while(j<k && *j==*(j-1)){
                            j++;
                        }
                        while(j<k && *(k+1)==*k){
                            k--;
                        }
                    }
                    else if(t<0){
                        j++;
                    }
                    else if(t>0){
                        k--;
                    }
                }
            }
            return res;
        }
    };