3Sum Solutions in C++

// Source : https://oj.leetcode.com/problems/3sum/
// Author : Hao Chen
// Date   : 2014-07-22



#include <stdio.h>
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;


/*
 *   Similar like "Two Number" problem, we can have the simlar solution.
 *
 *   Suppose the input array is S[0..n-1], 3SUM can be solved in O(n^2) time on average by 
 *   inserting each number S[i] into a hash table, and then for each index i and j,  
 *   checking whether the hash table contains the integer - (s[i]+s[j])
 *
 *   Alternatively, the algorithm below first sorts the input array and then tests all 
 *   possible pairs in a careful order that avoids the need to binary search for the pairs 
 *   in the sorted list, achieving worst-case O(n^n)
 *
 *   Solution:  Quadratic algorithm
 *   http://en.wikipedia.org/wiki/3SUM
 *
 */
vector<vector<int> > threeSum(vector<int> &num) {

    vector< vector<int> > result;
    if(num.size() == 0 || num.size() == 1 || num.size() == 2) return result;

    //sort the array, this is the key
    sort(num.begin(), num.end());

    int n = num.size();

    for (int i=0; i<n-2; i++) {
        //skip the duplication
        if (i > 0 && num[i - 1] == num[i]) continue;
        int a = num[i];
        int low = i + 1;
        int high = n - 1;
        while (low < high) {
            int b = num[low];
            int c = num[high];
            if (a + b + c == 0) {
                //got the soultion
                vector<int> v;
                v.push_back(a);
                v.push_back(b);
                v.push_back(c);
                result.push_back(v);
                // Continue search for all triplet combinations summing to zero.
                //skip the duplication
                while(low < n - 1 && num[low] == num[low + 1]) low++; 
                while(high > 0 && num[high] == num[high - 1]) high--; 
                low++;
                high--;
            } else if (a+b+c > 0) {
                //skip the duplication
                while(high > 0 && num[high] == num[high - 1]) high--;
                high--;
            } else {
                //skip the duplication
                while(low < n - 1 && num[low] == num[low + 1]) low++;
                low++;
            } 
        }
    }
    return result;
}

//using combination method could meet <<Time Limit Exceeded>> error
vector<vector<int> > combination(vector<int> &v, int k);
bool isSumZero(vector<int>& v);
int sum(vector<int>& v);

vector<vector<int> > threeSum2(vector<int> &num) {
    vector< vector<int> > result;
    vector< vector<int> > r = combination(num, 3);
    for (int i = 0; i < r.size(); i++) {
        if (isSumZero(r[i])) {
            result.push_back(r[i]);
        }
    }
    return result;
}

bool isSumZero(vector < int>& v) {
    return sum(v) == 0;
}

int sum(vector<int>& v) {
    int s = 0;
    for(int i = 0; i < v.size(); i++) {
        s += v[i];
    }
    return s;
}

vector<vector<int> > combination(vector<int> &v, int k) {

    vector<vector<int> > result;
    vector<int> d;
    int n = v.size();
    for (int i = 0; i < n; i++) {
        d.push_back( (i < k) ? 1 : 0 );
    }

    //1) from the left, find the [1,0] pattern, change it to [0,1]
    //2) move all of the 1 before the pattern to the most left side
    //3) check all of 1 move to the right
    while(1) {
        vector<int> tmp;
        for(int x = 0; x < n; x++) {
            if (d[x]) tmp.push_back(v[x]);
        }
        sort(tmp.begin(), tmp.end());
        result.push_back(tmp);
        //step 1), find [1,0] pattern
        int i;
        bool found = false;
        int ones = 0;
        for(i = 0; i < n - 1; i++) {

            if (d[i] == 1 && d[i + 1] == 0) {
                d[i] = 0; d[i + 1] = 1;
                found = true;
                //step 2) move all of right 1 to the most left side
                for (int j = 0; j < i; j++) {
                    d[j] = ( ones > 0 ) ? 1 : 0;
                    ones--;
                }
                break;
            }
            if (d[i] == 1) ones++;
        }
        if (!found) {
            break;
        }

    }
    return result;
}


void printMatrix(vector<vector<int> > &matrix)
{
    for(int i = 0; i < matrix.size(); i++) {
        printf("{");
        for(int j = 0; j < matrix[i].size(); j++) {
            printf("%3d ", matrix[i][j]) ;
        }
        printf("}\n");
    }
    cout << endl;
}


int main()
{
    //int a[] = { -1, 0, 1, 2, -1, 1, -4 };
    int a[] = { -1, 1, 1, 1, -1, -1, 0,0,0 };
    vector<int> n(a, a + sizeof(a)/sizeof(int));
    vector< vector<int> > result = threeSum(n);
    printMatrix(result);    
    return 0;
}

/// Source : https://leetcode.com/problems/3sum/
/// Author : liuyubobobo
/// Time   : 2016-12-03

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

/// Using Hash Table to store all the numbers
///
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        unordered_map<int, int> counter;
        for(int i = 0 ; i < nums.size() ; i ++)
            counter[nums[i]] ++;

        vector<vector<int>> res;

        if(counter[0] >= 3)
            res.push_back({0, 0, 0});

        // Remove duplication
        sort(nums.begin(), nums.end());
        vector<int>::iterator iter = unique(nums.begin(), nums.end());
        nums.erase(iter, nums.end());

        for(int i = 0 ; i < nums.size() ; i ++)
            for(int j = i + 1 ; j < nums.size() ; j ++){

                if(nums[i] * 2 + nums[j] == 0 && counter[nums[i]] >= 2)
                    res.push_back({nums[i], nums[i], nums[j]});

                if(nums[i] + nums[j] * 2 == 0 && counter[nums[j]] >= 2)
                    res.push_back({nums[i], nums[j], nums[j]});

                int c = 0 - nums[i] - nums[j];
                if(c > nums[j] && counter[c] != 0)
                    res.push_back({nums[i], nums[j], c});
            }

        return res;
    }
};

int main() {

    vector<int> nums1 = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> res = Solution().threeSum(nums1);
    for( int i = 0 ; i < res.size() ; i ++ ){
        for( int j = 0 ; j < res[i].size() ; j ++ )
            cout<<res[i][j]<<" ";
        cout<<endl;
    }

    return 0;
}

/// Source : https://leetcode.com/problems/3sum/
/// Author : liuyubobobo
/// Time   : 2016-12-03

#include <iostream>
#include <vector>
#include <cassert>
#include <stdexcept>

using namespace std;


/// Using two pointer technique
/// Time Complexity: O(n^2)
/// Space Complexity: O(n)
class Solution {

public:
    vector<vector<int>> threeSum(vector<int>& nums) {

        sort(nums.begin(), nums.end());

        vector<vector<int>> res;

        int index = 0;
        while( index < nums.size() ){

            if( nums[index] > 0 )
                break;

            int bindex = index + 1;
            int cindex = nums.size()-1;
            while( bindex < cindex) {

                if (nums[bindex] + nums[cindex] == -nums[index]) {
                    res.push_back({nums[index], nums[bindex], nums[cindex]});

                    // continue to look for other pairs
                    bindex = next_num_index( nums, bindex );
                    cindex = pre_num_index( nums, cindex);
                }
                else if (nums[bindex] + nums[cindex] < -nums[index])
                    bindex = next_num_index( nums, bindex );
                else //nums[bindex] + nums[cindex] > -nums[index]
                    cindex = pre_num_index( nums, cindex);
            }

            index = next_num_index( nums , index );
        }

        return res;
    }

private:
    int next_num_index( const vector<int> &nums, int cur ){

        for( int i = cur + 1; i < nums.size() ; i ++ )
            if( nums[i] != nums[cur] )
                return i;
        return nums.size();
    }

    int pre_num_index( const vector<int> &nums, int cur){

        for( int i = cur - 1; i >= 0 ; i -- )
            if( nums[i] != nums[cur] )
                return i;
        return -1;
    }
};

int main() {

    vector<int> nums1 = {-1, 0, 1, 2, -1, -4};
    vector<vector<int>> res = Solution().threeSum(nums1);
    for( int i = 0 ; i < res.size() ; i ++ ){
        for( int j = 0 ; j < res[i].size() ; j ++ )
            cout<<res[i][j]<<" ";
        cout<<endl;
    }

    return 0;
}