3Sum Closest Solutions in C++

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



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

using namespace std;

#define INT_MAX 2147483647
//solution:  http://en.wikipedia.org/wiki/3SUM
//the idea as blow:
//  1) sort the array.
//  2) take the element one by one, calculate the two numbers in reset array.
//
//notes: be careful the duplication number.
//
// for example:
//    [-4,-1,-1,1,2]    target=1
// 
//    take -4, can cacluate the "two number problem" of the reset array [-1,-1,1,2] while target=5
//    [(-4),-1,-1,1,2]  target=5  distance=4
//           ^      ^ 
//    because the -1+2 = 1 which < 5, then move the `low` pointer(skip the duplication)
//    [(-4),-1,-1,1,2]  target=5  distance=2
//                ^ ^ 
//    take -1(skip the duplication), can cacluate the "two number problem" of the reset array [1,2] while target=2
//    [-4,-1,(-1),1,2]  target=2  distance=1
//                ^ ^ 
int threeSumClosest(vector<int> &num, int target) {
    //sort the array
    sort(num.begin(), num.end());

    int n = num.size();
    int distance = INT_MAX;
    int result;

    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;
        //convert the 3sum to 2sum problem
        while (low < high) {
            int b = num[low];
            int c = num[high];
            int sum = a + b + c;
            if (sum - target == 0) {
                //got the final soultion
                return target;
            } else {
                //tracking the minmal distance
                if (abs(sum - target) < distance ) {
                    distance = abs(sum - target);
                    result = sum;
                }

                if (sum - target > 0) {
                    //skip the duplication
                    while(high > 0 && num[high] == num[high - 1]) high--;
                    //move the `high` pointer
                    high--;
                } else {
                    //skip the duplication
                    while(low < n && num[low] == num[low + 1]) low++;
                    //move the `low` pointer
                    low++;
                }
            }
        }
    }

    return result;
}




int main()
{
    int a[] = { -1, 2, 1, -4 };
    vector<int> n(a, a + sizeof(a)/sizeof(int));
    int target = 1;
    cout << threeSumClosest(n, target) << endl;
    return 0;
}

#include <vector>
#include <algorithm>
using std::vector; 

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        std::sort(num.begin(), num.end());
        int min{INT_MAX}, sum{0}, tmpsum{0};
        for (auto it=num.cbegin(); it!=num.cend(); ++it)
            for (auto b = std::next(it), e = std::prev(num.cend()); b<e; tmpsum > target ? --e : ++b)
                if ((tmpsum = *it + *b + *e) == target) return target;
                else if (std::abs(tmpsum - target) < min) {sum = tmpsum; min = std::abs(tmpsum - target);}
        return sum;
    }
};

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

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

using namespace std;


/// Sorting + Two Pointers
/// Time Complexity: O(nlogn) + O(n^2)
/// Space Complexity: O(1)
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {

        assert(nums.size() >= 3);

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

        int diff = abs(nums[0] + nums[1] + nums[2] - target);
        int res = nums[0] + nums[1] + nums[2];

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

            int l = i + 1, r = nums.size() - 1;
            int t = target - nums[i];
            while(l < r){
                if(nums[l] + nums[r] == t)
                    return nums[i] + nums[l] + nums[r];
                else{

                    if(abs(nums[l] + nums[r] - t) < diff){
                        diff = abs(nums[l] + nums[r] - t);
                        res = nums[i] + nums[l] + nums[r];
                    }

                    if( nums[l] + nums[r] < t )
                        l ++;
                    else   // nums[l] + nums[r] > t
                        r --;
                }
            }
        }

        return res;
    }
};


int main() {

    vector<int> nums1 = {0, 0, 0};
    int target1 = 1;
    cout << Solution().threeSumClosest(nums1, target ) << endl;

    return 0;
}