leetcode筆記：3Sum Closest

一.題目描述

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