2.5　最接近的三數之和

題目描述（第16題）

給定一個包括n個整數的數組nums和一個目標值target。找出nums中的3個整數，使它們的和與target最接近。返回這3個數的和。假定每組輸入只存在唯一答案。

例如，給定數組nums=[-1,2,1,-4]和target=1。

與target最接近的3個數的和為2，即-1+2+1=2。

思路

和上面三數之和的題目描述幾乎一樣，唯一不同的是，這次數組中的3個數相加可能永遠達不到target，這里要返回三數相加最接近target的和，從數學角度說就是三數之和與target的差的絕對值最小。

和上面的思路一樣，仍然先進行排序，然后固定1個元素，內部循環使用雙指針即可。唯一不同的是判斷邏輯有所不同，不再是三數之和等于target，而是三數之和與target的差的絕對值最小。由于題目要求返回3個數之和，因此用一個變量res去記錄3個數相加的和，如果該和與target的差的絕對值更小，就去更新res。

代碼

復雜度分析

●　時間復雜度：和三數之和一樣，時間復雜度為O(n2)。

●　空間復雜度：不確定，取決于內部排序算法的具體實現。

n數和問題是力扣（LeetCode）比較經典的系列題目之一，我們從最經典的兩數之和、三數之和、四數之和開始，到最接近的三數之和，以及四數之和II，不難發現它們有著很強的關聯性。希望讀者從這些題目中可以找到規律和“套路”，不管是思路上、解法上，還是代碼模板上。