LeetCode: 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)

---

Since the output should be in non-descending order, we can sort the input list first. And then for each element, we can use two iterators to try to find two elements that sum up to the negative value of the first one.

C++ Code:

/*
 * func: three_sum
 * goal: find three elements in an array which sum up to 0
 * @param num: the input array
 * return: vector of all unique triples
 */
/*
 * Sort the vector first, and then use two pointers to find the
 * answer.
 * Complexity: time O(n^2), space O(1)
 */
vector<vector<int> > three_sum(vector<int> &num){
    vector<vector<int> > ret;
    vector<int> candidate;
    if(num.size() <= 2){
        return ret;
    }
    //Sort the list first
    sort(num.begin(), num.end());
    
    for(int i = 0; i < num.size()-2 && num[i] <= 0; ++i){
        //Remove duplicates
        if(i > 0 && num[i] == num[i-1]){
            continue;
        }
        
        //Use two iters to find b and c which sum up tp -a
        int left = i+1, right = static_cast<int>(num.size())-1;
        while(left < right){
            int sum = num[i] + num[left] + num[right];
            if(sum < 0){
                ++left;
            }else if(sum > 0){
                --right;
            }else{
                //We find one choice
                candidate.emplace_back(num[i]);
                candidate.emplace_back(num[left]);
                candidate.emplace_back(num[right]);
                ret.emplace_back(candidate);
                candidate.clear();
                //Move iters to avoid duplicates
                do{
                    ++left;
                }while(left < right && num[left] == num[left-1]);
                
                do{
                    --right;
                }while(left < right && num[right] == num[right+1]);
            }
        }
    }
    return ret;
}

Python Code:

# func: find combinations of three elements in a list that sum up to 0
# @param num: input number list
# @result: a list of lists
def three_sum(num):
    if len(num) <= 2:
        return []
    else:
        #Sort the list first
        num.sort()
        result = []
        i = 0
        #Here we can add num[i] <= 0 to speed up because if the first element is
        #larger than 0, then there won't be problems
        while i < len(num)-2 and num[i] <= 0:
            #Remove duplicates
            if i > 0 and num[i] == num[i-1]:
                i += 1
                continue
            else:
                left = i+1
                right = len(num)-1
                while left < right:
                    sum = num[i] + num[left] + num[right]
                    if sum < 0:
                        left += 1
                    elif sum > 0:
                        right -= 1
                    else:
                        #Find one
                        result.append([num[i], num[left], num[right]])
                        #remove duplicates and keep going
                        while left < right and num[left+1] == num[left]:
                            left += 1
                        left += 1

                        while left < right and num[right-1] == num[right]:
                            right -= 1
                        right -= 1
            i += 1
        return result

Reference Link:

1.3Sum - LeetCode: http://discuss.leetcode.com/questions/15/3sum