题目
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1 输出：2 解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。
示例 2：
输入：nums = [0,0,0], target = 1 输出：0 解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。
解析
整体思路和LeetCode Hot 100：15. 三数之和-CSDN博客 非常类似，代码也是基于 三数之和 进行改编。
排序后，枚举 nums[i] 作为第一个数，那么问题变成找到另外两个数，使得这三个数的和与 target 最接近，这同样可以用双指针解决。
设 s=nums[i]+nums[j]+nums[k]，为了判断 s 是不是与 target 最近的数，我们还需要用一个变量 minDiff 维护 ∣s−target∣ 的最小值。分类讨论：
- 如果 s=target，那么答案就是 s，直接返回 s。
- 如果 s>target，那么如果 s−target<minDiff，说明找到了一个与 target 更近的数，更新 minDiff 为 s−target，更新答案为 s。然后和三数之和一样，把 k 减一。
- 否则 s<target，那么如果 target−s<minDiff，说明找到了一个与 target 更近的数，更新 minDiff 为 target−s，更新答案为 s。然后和三数之和一样，把 j 加一。
除此以外，还有以下几个优化：
- 设 s=nums[i]+nums[i+1]+nums[i+2]。如果 s>target，由于数组已经排序，后面无论怎么选，选出的三个数的和不会比 s 还小，所以不会找到比 s 更优的答案了。所以只要 s>target，就可以直接 break 外层循环了。在 break 前判断 s 是否离 target 更近，如果更近，那么更新答案为 s。
- 设 s=nums[i]+nums[n−2]+nums[n−1]。如果 s<target，由于数组已经排序，nums[i] 加上后面任意两个数都不超过 s，所以下面的双指针就不需要跑了，无法找到比 s 更优的答案。但是后面还有更大的 nums[i]，可能找到一个离 target 更近的三数之和，所以还需要继续枚举，continue 外层循环。在 continue 前判断 s 是否离 target 更近，如果更近，那么更新答案为 s，更新 minDiff 为 target−s。
- 如果 i>0 且 nums[i]=nums[i−1]，那么 nums[i] 和后面数字相加的结果，必然在之前算出过，所以无需跑下面的双指针，直接 continue 外层循环。（可以放在循环开头判断。）
作者：灵茶山艾府
链接：https://leetcode.cn/problems/3sum-closest/solutions/2337801/ji-zhi-you-hua-ji-yu-san-shu-zhi-he-de-z-qgqi/
来源：力扣（LeetCode）
答案
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
const n = nums.length;
if(n === 3) return nums[0] + nums[1] + nums[2];
nums.sort((a, b) => a - b);
let min_l = 10000, ans = 0;
for(let i = 0; i < n - 2; i++) {
if(i > 0 && nums[i] === nums[i-1]) continue; //跳过之前计算过的重复数字
// 和后面两个最小的数之和都大于target，i再增大，三数之和与target差距只会更大
let s = nums[i] + nums[i+1] + nums[i+2];
if(s > target) {
if(s - target < min_l) { //如果s与target更接近，更新答案
ans = s;
}
break; //直接跳出外层循环，返回答案
}
// 和最后两个最大的数之和都小于target
s = nums[i] + nums[n-2] + nums[n-1];
if(s < target) {
if(target - s < min_l) { //如果s与target更接近，更新答案
min_l = target - s;
ans = s;
}
continue; //返回外层循环，让i增大找更大的数（可能使三数之和更接近target）
}
let j = i + 1, k = n - 1;
while(j < k) {
s = nums[i] + nums[j] + nums[k];
if(s === target) return target;
if(s < target) {
if(target - s < min_l) {
min_l = target - s;
ans = s;
}
j++;
} else {
if(s - target < min_l) {
min_l = s - target;
ans = s;
}
k--;
}
}
}
return ans;
};复杂度分析
时间复杂度：O(n^2 )，其中 n 为 nums 的长度。排序 O(nlogn)。外层循环枚举第一个数，然后 O(n) 双指针。所以总的时间复杂度为 O(n^2 )。
空间复杂度：O(1)。返回值不计入，忽略排序的栈开销。
作者：灵茶山艾府
链接：https://leetcode.cn/problems/3sum-closest/solutions/2337801/ji-zhi-you-hua-ji-yu-san-shu-zhi-he-de-z-qgqi/
来源：力扣（LeetCode）