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.
For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Answer:
Similar to "3 Sum", additionally add a minv to track |a+b+c-target|, find the smallest value.
class Solution {
public:
int threeSumClosest(vector<int> &num, int target) {
int minv = INT_MAX, res;
int flag = 0;
sort(num.begin(), num.end());
for (int i = 0;i < num.size(); i++) {
if(i>0 && num[i]==num[i-1]) continue;
int j = i + 1;
int k = num.size() - 1;
while (j < k) {
int sum = num[i] + num[j] + num[k];
if ( sum < target) {
if(target - sum < minv){
minv = target - sum;
res = sum;
}
j++;
}
else if ( sum > target) {
if(sum - target < minv){
minv = sum - target;
res = sum;
}
k--;
}
else {
minv = 0;
res = sum;
flag = 1;
break;
}
}
if(flag)break;
}
return res;
}
};
No comments:
Post a Comment