## 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;
}
};

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});