LeetCode 3Sum Closest：閾值法優化三數之和最接近目標值

題目描述

給定整數數組 num 和目標值 target，找出三個數的和使其與 target 的絕對差最小。返回該和。假設唯一解。

解題技巧：動態閾值

排序數組後，雙指針遍歷。關鍵在於初始閾值 ThreadHold 的設置，根據 target 與可能的三數之和範圍 [MinSum, MaxSum] 關係分三種情況：

• target ≤ MinSum：ThreadHold = MaxSum - target
• target ≥ MaxSum：ThreadHold = target - MinSum
• MinSum < target < MaxSum：ThreadHold = MaxSum - MinSum

遍歷過程中，若 |sum - target| < ThreadHold，更新答案與閾值。這比初始化為 INT_MAX 更直觀，避免溢出風險。

完整 C++ 代碼

class Solution {
public:
    int threeSumClosest(vector &num, int target) {
        int n = num.size();
        sort(num.begin(), num.end());
        int MaxSum = 3 * num[n-1], MinSum = 3 * num[0];
        int ThreadHold;
        if (target <= MinSum) ThreadHold = MaxSum - target;
        else if (target >= MaxSum) ThreadHold = target - MinSum;
        else ThreadHold = MaxSum - MinSum;

        int Result = 0;
        for (int i = 0; i < n-2; i++) {
            if (i > 0 && num[i] == num[i-1]) continue;
            int l = i+1, r = n-1;
            while (l < r) {
                int sum = num[i] + num[l] + num[r];
                if (sum == target) return sum;
                if (sum < target) {
                    if (target - sum < ThreadHold) { ThreadHold = target - sum; Result = sum; }
                    l++;
                } else {
                    if (sum - target < ThreadHold) { ThreadHold = sum - target; Result = sum; }
                    r--;
                }
            }
        }
        return Result;
    }
};

總結

本題核心為排序 + 雙指針 O(n^2)。閾值初始化技巧利用數組有序性確定邊界，簡化邏輯。去重優化可減少冗餘計算。