16. 3Sum Closest

這是上一篇三數之和的變體問題。

這一題給定一個整數陣列nums和一個目標值target。目標是在nums中找到三個整數，它們的和最接近（Closest）於target。最後，需要返回這三個整數的和。
題目保證每個輸入都只有一個唯一解，這意味著不需要擔心多個和都同樣接近target的情況。

解決這類尋找固定數量元素之和（例如2 Sum, 3 Sum, 4 Sum）的問題，一個高效且標準的方法是：排序 + 雙指針（Two Pointers)，這也跟上一篇一模一樣。

這題的解題思路是先對陣列nums進行排序。這是使用雙指針的前提，排序後才能有效率地移動指針來調整和的大小。
接著，使用一個外部迴圈遍歷排序後的陣列，固定第一個數a(nums[i])。
對於每個固定的a，需要在剩餘的子陣列中找到另外兩個數b和c(nums[L]和nums[R])，使得a + b + c最接近target。跟上一篇一樣，使用兩個指針：L（左指針）從i + 1開始，R（右指針）從n - 1（陣列末尾）開始。再來，計算當前的三數之和Sum = nums[i] + nums[L] + nums[R]。然後，根據Sum與target的關係來移動指針：如果Sum < target，表示和太小了，需要增加和的值，移動左指針L++（因為陣列已排序，nums[L]會變大）；如果Sum > target，表示和太大了，需要減少和的值，移動右指針R–（因為陣列已排序，nums[R]會變小）；如果Sum = target，意味著找到了精確的解，由於題目保證只有一個解，可以直接返回Sum。
最後，在每次計算Sum後，需要檢查它是否比當前找到的「最接近的和」更接近target。先維護一個變量closestSum來儲存目前找到的最接近的和。至於判斷標準，如果abs(Sum - target) < abs(closestSum - target)，則更新closestSum = Sum。為了初始化closestSum，可以直接用前三個數的和或一個極端值來初始化。

複雜度分析
時間複雜度（Time Complexity）：

排序：O(n log n)

外層迴圈遍歷n次，內層雙指針迴圈在最壞情況下會執行O(n)步。

總體時間複雜度：O(n log n + n^2) = O(n^2)。

空間複雜度（Space Complexity）：

如果使用java內建的Arrays.sort()（通常是Timesort），額外空間複雜度為O(log n)或O(n)，取決於具體的時限和輸入，但通常被認為是原地排序（In-place sort）。

這種排序 + 雙指針的方法比暴力解法的O(n^3)要高效得多，是解決這類k-Sum問題的標準做法。