## Finding sum of triplets that is closest to a given number (3Sum Closest)

Given an array $S$ of $n$ integers, find three integers in $S$ such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
INPUT: $S$ = {-1, 2, 1, -4} and target = 1
OUPUT: 2 since the sum that is closest to the target is 2 (-1 + 2 + 1 = 2).

Thoughts:
The approach should be similar to the problem 3sum. There are only two things we need to add:

1. If we have found a sum that is exactly the target, we can just return it since you cannot find a even closer sum that the target itself.
2. Along the search, we keep a record of current closest sum and the corresponding difference between it and the target. We then updae those two variables as we go.

Code (Java):

```public class Solution {
public int threeSumClosest(int[] num, int target) {
int sol = target;
int min_diff = Integer.MAX_VALUE;
Arrays.sort(num);
for(int i = 0; i < num.length; ++i) {
int low = i + 1;
int high = num.length - 1;
while(low < high) {
int sum = num[i] + num[low] + num[high];
if(sum == target)
return sum;
else if(sum > target) {
int diff = Math.abs(sum - target);
if(diff < min_diff) {
min_diff = diff;
sol = sum;
}
high--;
} else { // sum < target
int diff = Math.abs(sum - target);
if(diff < min_diff) {
min_diff = diff;
sol = sum;
}
low++;
}
}
}
return sol;
}
}

Code (C++):
class Solution {
public:
int threeSumClosest(vector<int> &num, int target) {
int sol = target;
int min_diff = INT_MAX;
sort(num.begin(), num.end());
for(int i = 0; i < num.size(); ++i) {
int low = i + 1;
int high = num.size() - 1;
while(low < high) {
int sum = num[i] + num[low] + num[high];
if(sum == target)
return sum;
else if(sum > target) {
int diff = abs(sum - target);
if(diff < min_diff) {
min_diff = diff;
sol = sum;
}
high--;
} else { // sum < target
int diff = abs(sum - target);
if(diff < min_diff) {
min_diff = diff;
sol = sum;
}
low++;
}
}
}
return sol;
}
};

div.wpmrec2x{max-width:610px;}
div.wpmrec2x div.u > div{float:left;margin-right:10px;}
div.wpmrec2x div.u > div:nth-child(3n){margin-right:0px;}

(function(g,\$){if("undefined"!=typeof g.__ATA){
}})(window,jQuery);

var o = document.getElementById('crt-49558900');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');
} else {
o.style.setProperty('display', 'none', 'important');
o.style.setProperty('visibility', 'hidden', 'important');
}

var o = document.getElementById('crt-943783523');
if ("undefined"!=typeof Criteo) {
var p = o.parentNode;
p.style.setProperty('display', 'inline-block', 'important');
o.style.setProperty('display', 'block', 'important');