Lintcode: 3 Sum

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.

Have you met this question in a real interview? 

Yes

Example

For example, given array S = {-1 0 1 2 -1 -4}, A solution set is:

(-1, 0, 1)
(-1, -1, 2)

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.

Tags Expand 

Two Pointers Sort Array

3 sum is based on 2 sum problem. 2 sum problems have two solutions: one is hashmap, the other is sorting.
Since the solution set cannot repeat and elements are in non-descending order. If we use hashmap, it will be complex to deal with repetition. So we use sorting.

Sorting first, then iterate each element and use front and end pointers to search for sum = target - cur.
Time: O(nlogn) + O(n2) = O(n2)
Space: O(n)
Reference: http://www.programcreek.com/2012/12/leetcode-3sum/
                  http://bangbingsyb.blogspot.com/2014/11/leetcode-3sum.html

Note: see an interesting solution with O(nlogn + n2 *logn) =O(n^2*logn)
Sorting first, then iteration two sums and use binary search to find the third element.
http://blog.unieagle.net/2012/08/22/leetcode%E9%A2%98%E7%9B%AE3sum/

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int> > result;
        if(nums.size() < 3) return result;
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size() - 2; i++){
          if(i == 0 || nums[i] != nums[i - 1]){
            int sum = -nums[i];
            int start = i + 1;
            int end = nums.size() - 1;
            while(start < end){
                if(nums[start] + nums[end] == sum){
                    vector<int> temp;
                    temp.push_back(nums[i]);
                    temp.push_back(nums[start]);
                    temp.push_back(nums[end]);
                    result.push_back(temp);
                    temp.clear();
                    while(start < end && nums[start] == nums[start + 1]){
                        start++;
                    }
                    while(end > start && nums[end] == nums[end - 1]){
                        end--;
                    }
                    start++;
                    end--;
                }else if(nums[start] + nums[end] < sum){
                    start++;
                }else{
                    end--;
                }
                
            }
           }
        }
        return result;
    }
};

Second lintcode:
failed hashmap solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

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 unordered_map<int, unordered_map<int> > hash1; for(int i = 0; i < nums.size(); i++){ hash1[nums[i]].insert(i); } unordered_map<int, hash_set<pair<int, int> > > hash2; for(int i = 0; i < nums.size(); i++){ for(int j = i + 1; j < nums.size(); j++){ //check repetation(two kind repetations: one is different indexes but same numbers, the other is repetations of indexed when try to find the third c but the index of c is same with a or b)(e.g. 1, 1 , -2 ; 0 0 0) int sum = nums[i] + nums[j]; //check first type repetation int minV = min(nums[i], nums[j]); int maxV = max(nums[i], nums[j]); pair<int, int> curP = make_pair(minV, maxV); if(hash2.count(sum) && hash2[sum].count(curP) ) continue; //check second type repetation if(!hash1.count(-sum)) continue; //when nums[i] == nums[j] == -sum if(hash1[-sum].count(i) && hash1[-sum].count(j) && hash1[-sum].size() <= 2) continue; //when nums[i] == -sum if(hash1[-sum].count(i) && hash1[-sum].size() == 1) continue; //when nums[j] == - sum if(hash1[-sum].count(j) && hash1[-sum].size() == 1) continue; //now we can sure i , j , and there exists another element that makes sum = 0 //but it's possible that the three numbers together appeared before } } } };