一.題目描述
二.解題技巧<喎?http://www.Bkjia.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的關系來設定阈值了,具體的阈值設置情況可以畫個數軸出來分析,畫出數軸之後,一切就明顯了。