最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近

返回这三个数的和

假定每组输入只存在恰好一个解

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

测试用例

用例1：

• 输入：nums = [-1,2,1,-4], target = 1
• 输出：2
• 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)

用例2

• 输入：nums = [0,0,0], target = 1
• 输出：0

思路

三数之和要先枚举第一个数，把问题转为求另外两个数 —— 双指针

三个数的和s与target取绝对值 —— 绝对值最小，越接近 —— 用diffMin维护|s-target|的最小值

1. 如果s - target = 0，则答案就是s，直接返回
2. 如果s - target > 0, 判断此时的s - target是否小于diffMin, 如果小于了，就证明找到了一个更接近target的和，更新diffMin, 同时右指针减1
3. 如果s - target < 0, 判断此时的target - s是否小于diffMin, 如果小于了，就证明找到了一个更接近target的和，更新diffMin, 同时左指针加1

代码实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    // 最接近
    // 三数之和先枚举第一个数，把问题转为求另外两个数 —— 双指针
    // 三个数的和s与target取绝对值 —— 绝对值最小，越接近 —— 用diffMin维护|s-target|的最小值

    // 1. 如果s - target = 0，则答案就是s，直接返回
    // 2. 如果s - target > 0, 判断此时的s - target是否小于diffMin, 如果小于了，就证明找到了一个更接近target的和，更新diffMin, 同时右指针减1
    // 3. 如果s - target < 0, 判断此时的target - s是否小于diffMin, 如果小于了，就证明找到了一个更接近target的和，更新diffMin, 同时左指针加1

    // 排序
    nums.sort((a, b) => a - b);
    // 记录结果
    let ans = 0;
    // 记录和
    let s = 0;
    // 维护|s-target|
    let diffMin = Number.MAX_SAFE_INTEGER;
    
    for(let i = 0; i < nums.length - 2; i ++){
        const cur = nums[i];
        let l = i + 1;
        let r = nums.length - 1;
        
        // 去重优化
        if(i > 0 && nums[i] === nums[i - 1]){
            continue;
        }

        // 和最大值优化 —— 但要判断是否是最优解
        let sMax = cur + nums[i + 1] + nums[i + 2];
        if(sMax > target){
            if(sMax - target < diffMin){
                ans = sMax;
            }
            break;
        }

        // 开始枚举
        while(l < r){
            s = cur + nums[l] + nums[r]; 
            if(s - target === 0){
                ans = s;
                return ans;
            }
            else if(s - target > 0){
                // 是否更新diffMin
                if(s - target < diffMin){
                    diffMin = s - target;
                    ans = s;
                }
                // 去重判断
                while(i < r && nums[r] === nums[r - 1]){
                    r --;
                }
                r --;
            }
            else{
                if(target - s < diffMin){
                    diffMin = target - s;
                    ans = s;
                }
                while(l < r && nums[l] === nums[l + 1]){
                    l ++;
                }
                l ++;
            }
        }
    }
    return ans;
};