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)

tags: array, two pointers

老规矩，先暴力搜，看看能不能过。
n^3复杂度，倒不是超时，而是输出超界(OUTPUT LIMIT EXCEEDED)。看来原数组中有很多重复数字，导致我产生了过多的重复解(duplicate)，尝试优化中。

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>> re;
        for(vector<int>::iterator it1 = num.begin(); it1 != num.end(); it1++){
            for(vector<int>::iterator it2 = it1; it2 != num.end(); it2++){
                for(vector<int>::iterator it3 = it2; it3 != num.end(); it3++){
                    if(*it1 + * it2 + *it3 == 0){
                        vector<int> thisRe;
                        thisRe.push_back(*it1);
                        thisRe.push_back(*it2);
                        thisRe.push_back(*it3);
                        sort(thisRe.begin(), thisRe.end());
                        re.push_back(thisRe);
                    }
                }
            }
        }
        return re;
    }
};

2.2更新

利用一个哈希表，储存个元素出现的次数，将复杂度降到n^2。对原始序列进行排序，谨慎地控制指针的移动从而避免出现重复解。

需要注意解集中出现的重复数字，比如(2,2,-4)这样，先要判断提供的序列中元素的个数是否足够，然后再压入返回值中。

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int>> re;
        unordered_map<int, int> m;
        if(num.empty() == true || num.size() < 3){
            return re;
        }
        sort(num.begin(), num.end());
        for(vector<int>::iterator it = num.begin(); it != num.end(); it++){
            if(m.find(*it) == m.end()){
                m[*it] = 1;    
            }
            else{
                m[*it]++;
            }
        }
        vector<int>::iterator it1 = num.begin();
        while(it1!= num.end()){
            vector<int>::iterator it2 = it1 + 1;
            while(it2 != num.end()){
                int a = *it1;
                int b = *it2;
                int target = 0 - a - b;
                if(target < b){//repeated possible result
                    break;
                }
                else if(m.find(target) != m.end()){//found
                    int count = m[target];
                    if((a == b && a == target && count < 3) || ((target == b) && count < 2)){
                        //not enough num
                        ;
                    }
                    else{
                        vector<int> thisRe;
                        thisRe.push_back(a);
                        thisRe.push_back(b);
                        thisRe.push_back(target);
                        re.push_back(thisRe);
                    }
                }
                it2++;
                while(*it2 == *(it2-1) && it2 != num.end()){
                    it2++;
                }
            }
            /*move it1 */
            it1++;
            while(*it1 == *(it1 - 1) && it1 != num.end()){
                it1++;
            }
        }
        return re;
    }
};