LeetCode 16. 最接近的三數之和：排序雙指針優化解法（Java）

題目要求：給定整數數組 nums 與目標值 target，找出三個整數使其和與 target 最接近，返回該三數之和。假設每組輸入僅有一個答案。

暴力遞歸 vs 排序雙指針

暴力三層循環 O(N³) 會超時。排序 + 雙指針 可降至 O(N²)：

1. 數組排序。
2. 固定第一個數 i，剩餘區間 [i+1, n-1] 雙指針 L、R 向中間收縮。
3. 計算 sum = nums[i] + nums[L] + nums[R]，更新最小差值 gap。
4. 若 sum < target 則 L++（需增大和）；若 sum > target 則 R--（需減小和）；相等直接返回。
5. 跳過重複元素優化（可選）。

Java 實現

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++) {
            if (i > 0 && nums[i] == nums[i-1]) continue; // 跳過重複
            int L = i + 1, R = n - 1;
            while (L < R) {
                int sum = nums[i] + nums[L] + nums[R];
                if (sum == target) return target; // 完美匹配
                
                if (Math.abs(sum - target) < Math.abs(closest - target))
                    closest = sum;
                
                if (sum < target) L++;
                else R--;
            }
        }
        return closest;
    }
}

關鍵點圖解

複雜度分析

• 時間：O(N²) —— 排序 O(N log N) + 雙層遍歷 O(N²)。
• 空間：O(1)（不計排序棧空間）。

常見坑點

• 初始化 closest 必須用前三數之和，不可設為 0 或 Integer.MAX_VALUE。
• 更新 closest 時比較絕對差值，而非直接比較和值。
• 若允許重複三元組，需去重邏輯；本題保證唯一答案，去重非必須但可提速。