Problem：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).
吃饭之前刷了这题。思路就是和上题类似。先srot，然后固定i从第一个到倒数第三个，然后设一个left=i+1，right=num.size()-1; 如果三个数相加和target相比较大，那就right--，使三个数相加要变小。如果比target小那就left++。同时用abs记录当前的差值，如果比之前的差值更小，那就记录三个数的和到val中。如果差值为零了，那就直接返回三个数的和。否则到最后在返回val就可以了。代码如下
class Solution {
public:
int threeSumClosest(vector<int> &num, int target)
{
int left = , right = , val = , minC = INT_MAX;
sort(num.begin(), num.end());
for (int i = ; i < num.size() - ; ++i)
{
left = i + ; right = num.size() - ;
while(left < right)
{
int tepVal = target - num[i] - num[left] - num[right];
if (abs(tepVal) < minC)
{minC = abs(tepVal); val = num[i] + num[left] + num[right];}
if (tepVal > )
left++;
else if (tepVal < )
right--;
else
return num[i] + num[left] + num[right];
}
}
return val;
}
};
吃饭去了。
2015/4/3:
class Solution {
public:
int threeSumClosest(vector<int> &num, int target) {
sort(num.begin(), num.end());
int ans, globalVal = INT_MAX;
for (int i = ; i < num.size(); ++i){
if (i > && num[i] == num[i-])
continue;
int left = i+, right = num.size()-;
while(left < right){
int val =target - (num[i] + num[left] + num[right]);
if (abs(val) < globalVal){
ans = num[i] + num[left] + num[right];
globalVal = abs(val);
}
if (val == )
return target;
else if(val > )
left++;
else
right--;
}
}
return ans;
}
};