## 一.題目描述  ## 二.解題技巧 該題與3Sum的要求類似，不同的是要求選出的組合的和與目標值target最接近而不一定相等。但實際上，與3Sum的算法流程思路相似，先是進行排序，然后順序選擇數組A中的下標為i的元素值作為組合中三個數的最小值，進而尋找另外兩個更大的值，最后求出三個數的和。不過的地方在于這里是尋找最靠近給定值，尋找最靠近的值就無所有重復的事情了，所以可以不考慮夾逼的過程中的越過相同元素的過程，雖然越過相同的元素速度會快一些，但是代碼長度也會加長。 這道題難的地方可能在于剛開始這種差的閾值的過程，如果把閾值設置得太小了，會出現錯誤，因此，應該盡可能地將閾值設置得大一點。由于數組是已經排序的，因此，數組中三個數的和的范圍在[3*A[0], 3*A[n-1]]，因此，閾值可以根據下面三種情況進行設置： ~~~ 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<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; } }; ~~~ ## 四.總結 這道題最難的地方在于閾值的選擇上面，其實可以設置為整數的最大值的，但是，我一開始并不知道如何計算整數的最大值，因此，只能根據排好序的數組的三個數的和的范圍與target的關系來設定閾值了，具體的閾值設置情況可以畫個數軸出來分析，畫出數軸之后，一切就明顯了。