今天挑戰的題目是 3Sum Closest，這題跟前面做過的 3Sum 類似，但要求的是「最接近 target 的三數和」，而不是找出所有符合條件的組合。

題目重點

輸入一個整數陣列 nums 和一個整數 target。

從陣列中挑出三個數字，使得它們的總和最接近 target。

回傳這個三數的總和。

保證每個輸入一定有唯一解。

範例：

Input: nums = [-1,2,1,-4], target = 1
Output: 2 （因為 -1 + 2 + 1 = 2，距離 target=1 最近）

Input: nums = [0,0,0], target = 1
Output: 0

解題思路

這題跟 3Sum 一樣，可以先 排序陣列，然後用雙指標的方法來解決。

排序陣列，讓數字從小到大排列。

固定一個數字 nums[i]，再用左右指標 left、right 來搜尋另外兩個數字。

每次計算總和 sum = nums[i] + nums[left] + nums[right]：

如果 sum 剛好等於 target，直接回傳。

如果 sum 比 target 小，左指標右移。

如果 sum 比 target 大，右指標左移。

同時用一個變數 closest 記錄「目前找到的最接近 target 的總和」。

這樣的時間複雜度是 O(n^2)，在題目限制下是可以接受的。

程式碼範例 (Java)
import java.util.Arrays;

public class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int closest = nums[0] + nums[1] + nums[2]; // 先隨便取一組當初始值

    for (int i = 0; i < n - 2; i++) {
        int left = i + 1, right = n - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (Math.abs(sum - target) < Math.abs(closest - target)) {
                closest = sum;
            }
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                return sum; // 完全相等，直接回傳
            }
        }
    }
    return closest;
}

}

心得

這題看起來是 3Sum 的「簡化版」，不用輸出所有解，只要找出最接近 target 的和。
雖然邏輯簡單，但一開始我常犯的錯誤是：

沒有先初始化 closest，導致後面比大小出錯。

忘記更新 closest 的條件要用絕對值比較。