筆試題29. LeetCode OJ (16)

上個題絞盡腦汁的思考測試終於弄出結果了，所以遇到這個題的時候感覺松了口氣。這個題要求三個數的和最接近所給的數，

意思就是找一個數組中三個數的和，使它最接近你所給的目標。我的思路是遍歷，因為不遍歷完所有情況根本就無法推測結果，難

道大家還有別的做法能減少計算的次數嗎，我猜想如果排序後還是有可能的排序後能推測出數字的和范圍，這個辦法應該可行的,

但是仔細想想的話還是比較麻煩，需要考慮到的細節又會很多，因為我們需要的三個數並不一定是連續的三個數的，而且我們並不

知道"最接近的程度"是多大，這樣也是在盲目的測試，所以我覺得我還是采用遍歷的做法。

這個題需要注意的是若三個數的和等於target的話，那我們的工作不用繼續了，直接返回target就行。

遍歷的做法代碼如下：

 

class Solution {
public:
    int threeSumClosest(vector& nums, int target) 
    {
        int gap = 0; //差距，即和target的接近程度
        int sum = 0;
        int len = nums.size(); //元素個數
        if(len < 3)
        {
            return -1;
        }
        //初始化gap
        sum = nums[0]+nums[1]+nums[2];
        gap = target > sum ? (target-sum):(sum-target);
        for(int begin = 0 ; begin < len-2; ++begin)
        {
            if(begin > 0 && nums[begin] == nums[begin-1])
            {
                ++begin;
                continue;
            }
            int pos1 = begin+1;
            while(pos1 < len-1)
            {
                int pos2 = pos1+1;
                while(pos2 < len)
                {
                    int tmpsum = nums[begin] + nums[pos1]+nums[pos2];
                    if(tmpsum == target)
                    {
                        return target;
                    }
                    else if(abs(tmpsum - target) < gap)
                    {
                        sum = tmpsum;
                        gap = abs(tmpsum - target);
                    }
                    ++pos2;
                }
                ++pos1;
            }
        }
        return sum;
    }
};

但是我還是有一種沖動覺得排序在查找那種做法是有可能的，如果有誰知道思路請告訴我一下吧，謝謝。我自己也下去再

 

好好思考一下吧。

當然遍歷的做法是被接受的...