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).
题意:给定值target,在数列中找到三个数,它们的和最接近这个target。
思路:类似于Two sum、3sum还有本题,都可以先排序后,用夹逼法则:使用两个指针,从前向后,从后向前的遍历,找到符合条件的情况。为什么要使用这种方法了?针对本题,若是固定一个,然后再固定一个,通过移动最后一个指针,找到最小的差,然后,在重新将第二个指针移动一个位置,低三个指针,再重新遍历,这样耗时严重。利用好,已将数组排序这一条件,固定一个数,剩下的两个数分别从头和尾向中间遍历,若是三者的和大于target,则尾指针向左移动,减小对应的值,否则前指针右移增大对应的值,从而增大三者和。与此同时,更新和target最小的差和对应的sum。代码如下:
class Solution {
public:
int threeSumClosest(vector<int> &num, int target)
{
int sum=num[]+num[]+num[];
int diff=abs(sum-target);
sort(num.begin(),num.end()); for(int i=;i<num.size();++i)
{
int l=i+,r=num.size()-;
while(l<r)
{
int temp=num[i]+num[l]+num[r];
int newDiff=abs(temp-target); if(diff>newDiff)
{
diff=newDiff;
sum=temp;
}
if(temp>target)
r--;
else
l++;
}
}
return sum;
}
};