LeetCode 16 3Sum Closest：最接近目標值的三數之和

題目翻譯

給定整數陣列 S 與目標值 target，找出三數使其和最接近 target。假設唯一解。例：S = [-1,2,1,-4], target = 1 → 最近和為 2 (-1+2+1)。

解題思路：雙指針

1. 排序陣列。
2. 固定第一個數 current，左右指針 front、back 夾逼。
3. 計算三數和 sum，比較與 target 差值，更新最小差值與結果。
4. 根據 sum 大小移動指針，跳過重複值避免重複計算。

C++ 實現

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int len = nums.size();
        int result = INT_MAX, close = INT_MAX;
        for (int current = 0; current < len - 2; ++current) {
            int front = current + 1, back = len - 1;
            while (front < back) {
                int sum = nums[current] + nums[front] + nums[back];
                if (sum < target) {
                    if (target - sum < close) { close = target - sum; result = sum; }
                    ++front;
                } else if (sum > target) {
                    if (sum - target < close) { close = sum - target; result = sum; }
                    --back;
                } else {
                    return target; // 找到精確解直接返回
                }
            }
            while (current < len - 2 && nums[current+1] == nums[current]) ++current;
        }
        return result;
    }
};

相關題目

• LeetCode 15 3Sum：尋找和為 0 的所有三元組。
• LeetCode 18 4Sum：四數之和。