一.题目描述

二.解题技巧<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4NCjxwPrjDzOLT6zNTdW21xNKqx/PA4MvGo6yyu82stcTKx9Kqx/PRobP2tcTX6brPtcS6zdPrxL+x6ta1dGFyZ2V01+690738tviyu9K7tqjP4LXIoaO1q8q1vMrJz6Os0+szU3VttcTL47eowfezzMu8wrfP4MvGo6zPyMrHvfjQ0MXF0PKjrMi7uvPLs9Dy0aHU8cr91+lB1tC1xM/CserOqmm1xNSqy9jWtdf3zqrX6brP1tDI/bj2yv21xNfu0KHWtaOsvfi2+NGw1dLB7c3iwb249rj8tPO1xNa1o6zX7rrzx/Oz9sj9uPbK/bXEus2ho7K7uf21xLXYt73U2tPa1eLA78rH0bDV0tfuv7+9/Lj4tqjWtaOs0bDV0tfuv7+9/LXE1rW+zc7ey/nT0NbYuLS1xMrCx+nBy6Osy/nS1L/J0tSyu7+8wse80LHGtcS5/bPM1tC1xNS9uf3P4M2s1KrL2LXEuf2zzKOsy+TIu9S9uf3P4M2stcTUqsvYy9m2yLvhv+zSu9Cpo6y1q8rHtPrC67OktsjSsrvhvNOzpKGjPC9wPg0KPHA+1eK1wMzixNG1xLXYt72/ycTc1NrT2rjVv6rKvNXi1tay7rXE49DWtbXEuf2zzKOsyOe5+7DR49DWtcno1sO1w8yr0KHBy6Osu+Gz9s/WtO3O86Os0vK0y6Os06a4w76hv8nE3LXYvavj0Na1yejWw7XDtPPSu7XjoaPTydPayv3X6crH0tG+rcXF0PK1xKOs0vK0y6Osyv3X6dbQyP249sr9tcS6zbXEt7bOp9TaWzMqQVswXSwgMypBW24tMV1do6zS8rTLo6zj0Na1v8nS1Lj5vt3PwsPmyP3W1sfpv/a9+NDQyejWw6O6PC9wPg0KPHByZSBjbGFzcz0="brush:java;"> 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。

这样就可以根据阈值与目前得到的三个数的和与target的差来判断是否是最接近target的情况了，根据不同的情况，选择缩放的方向。

三.示例代码

class Solution  
{  
public:  
    int threeSumClosest(vector
   
     &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; } };
   

四.总结

这道题最难的地方在于阈值的选择上面，其实可以设置为整数的最大值的，但是，我一开始并不知道如何计算整数的最大值，因此，只能根据排好序的数组的三个数的和的范围与target的关系来设定阈值了，具体的阈值设置情况可以画个数轴出来分析，画出数轴之后，一切就明显了。

?