Given an array of integers, find three integers in 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: = {-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:

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

### Like this:

Like Loading...

*Related*