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的情况了，根据不同的情况，选择缩放的方向。1.if target >= 3*A[n-1],阈值设置为H = target - 3 * A[0];2.if 3*A[0] <= target<3*A[n-1],阈值设置为H = 3 * A[n-1] - 3*A[0];3.if target < 3 * A[0],阈值设置为H = 3 * A[n-1] - target。
class Solution
{
public:
int threeSumClosest(vector<int> &num, int target)
{
int Size = num.size();
sort(num.begin(), num.end());
int MaxSum = 3 * num[Size - 1];
int MinSum = 3 * num[0];
int ThreadHold = 0;
if (target <= MinSum)
{
ThreadHold = MaxSum - target;
}
if (MaxSum < target)
{
ThreadHold = target - MinSum;
}
if ((MinSum < target) && (target <= MaxSum))
{
ThreadHold = MaxSum - MinSum;
}
int Result = 0;
for (int Index_outter = 0; Index_outter < (Size - 2); Index_outter++)
{
int First = num[Index_outter];
int Second = num[Index_outter + 1];
if ((Index_outter != 0) && (First == num[Index_outter - 1]))
{
continue;
}
int Start = Index_outter + 1;
int End = Size - 1;
while (Start < End)
{
Second = num[Start];
int Third = num[End];
int Sum = First + Second + Third;
if (Sum == target)
{
return Sum;
}
if (Sum < target)
{
Start++;
if (ThreadHold >= (target - Sum))
{
Result = Sum;
ThreadHold = target - Sum;
}
}
if (Sum > target)
{
End--;
if (ThreadHold >= (Sum - target))
{
Result = Sum;
ThreadHold = Sum - target;
}
}
}
}
return Result;
}
};
原文：http://blog.csdn.net/sheng_ai/article/details/44319307