3 Sum

http://www.lintcode.com/en/problem/3sum/

Discussion

先排序，后夹逼，注意消除结果里面的重复三元组。 复杂度$$O(n^2)$$

Solution

class Solution {
public:    
    /**
     * @param numbers : Give an array numbers of n integer
     * @return : Find all unique triplets in the array which gives the sum of zero.
     */
    vector<vector<int> > threeSum(vector<int> &nums) {
        // write your code here
        vector<vector<int> > result;
        if (nums.size() < 3) return result;
        sort(nums.begin(), nums.end());
        for(vector<int>::iterator it = nums.begin(); it<nums.end()-2; it++) {
            vector<int>::iterator ita = it+1;
            vector<int>::iterator itb = nums.end()-1;
            while(ita < itb) {
                if(*it + *ita + *itb == 0) {
                    result.push_back({*it , *ita , *itb});
                    ita++;
                    itb--;
                } else if(*it + *ita + *itb < 0) {
                    ita++;
                } else {
                    itb--;
                }
            }
        }
        sort(result.begin(), result.end());
        vector<vector<int> >::iterator it = unique(result.begin(), result.end());
        result.resize(it-result.begin());
        return result;
    }
};

1. 要习惯用iterator遍历，方便，当然用下标也可以。
2. 结果是有可能存在重复元素的，比如输入[1,0,-1,-1,-1,-1,0,1,1,1]， 会返回好多[-1,0,1]
3. 去除vector里的重复元素的方法，先sort，再用unique返回the element that follows the last element not removed. 需要注意的是unique是不会改变vector的size的，需要调用resize或者erase函数。

    sort(result.begin(), result.end());
    vector<vector<int> >::iterator it = unique(result.begin(), result.end());
    result.resize(it-result.begin());//or result.resize(distance(result.begin(), it))
    // or result.erase(it, result.end());
   

4. 如果在遍历vector的元素就去除元素会更简单。注意要跳过第一个元素重复的情况，和记录重复的情况。as follows:

   class Solution {
   public:    
    /**
     * @param numbers : Give an array numbers of n integer
     * @return : Find all unique triplets in the array which gives the sum of zero.
     */
    vector<vector<int> > threeSum(vector<int> &nums) {
        // write your code here
        vector<vector<int> > result;
        vector<int> lastrecord;
        if (nums.size() < 3) return result;
        sort(nums.begin(), nums.end());
        for(vector<int>::iterator it = nums.begin(); it<nums.end()-2; it++) {
            vector<int>::iterator ita = it+1;
            vector<int>::iterator itb = nums.end()-1;
            if(it>nums.begin() && *it == *(it-1))
                continue;//第一个元素重复，说明已经遍历过了，跳过
            while(ita < itb) {
                if(*it + *ita + *itb == 0) {
                    vector<int> record = {*it , *ita , *itb};
                    if(lastrecord != record) {
                        result.push_back(record);
                        lastrecord = record;
                    }//给定第一个元素，第二三个元素也有可能重复，所以用lastrecord保存上一条记录。
                    ita++;
                    itb--;
                } else if(*it + *ita + *itb < 0) {
                    ita++;
                } else {
                    itb--;
                }
            }
        }
        return result;
    }
   };
   

更简洁的写法：

class Solution {
public:    
    /**
     * @param numbers : Give an array numbers of n integer
     * @return : Find all unique triplets in the array which gives the sum of zero.
     */
    vector<vector<int> > threeSum(vector<int> &nums) {
        vector<vector<int> > result;
        if(nums.empty()) return result;
        sort(nums.begin(), nums.end());
        for(auto it = nums.begin(); it<nums.end()-2; it++) {
            //skip duplicates
            if(it != nums.begin() && *(it) == *(it-1)) continue;
            auto ita = it+1;
            auto itb = nums.end() - 1;
            while(ita < itb) {
                //skipt duplicates
                if(distance(it, ita) > 1 && *ita == *(ita-1)) {ita++; continue;}
                if(distance(itb, nums.end()) > 1 && *itb == *(itb+1)) {itb--; continue;}
                if(*ita + *itb > -(*it)) {
                    itb--;
                } else if(*ita + *itb < -(*it)) {
                    ita++;
                } else {
                    result.emplace_back(vector<int>{*it, *ita, *itb});
                    ita++;
                    itb--;
                }
            }
        }
        return result;
    }
};