0016.最接近的三数之和
难度：🟡 中等
标签：数组、双指针、排序
链接：16. 最接近的三数之和
题目描述
给你一个长度为 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 最接近 的组合。其核心思想与“三数之和”类似，即通过固定一个数，将问题转化为在数组剩余部分寻找“两数之和”的问题。
思路选择
排序 + 双指针 是解决此问题的标准最优思路。
我们首先对数组进行排序，这为使用双指针高效地查找提供了前提。
我们遍历数组，固定第一个数
nums[i]。然后，在数组的剩余部分[i+1, n-1]中，使用左右两个指针left和right来寻找另外两个数。在每一步，我们计算当前三数之和
sum，并比较sum与target的差距。我们维护一个全局变量来记录并更新与target最接近的和。根据
sum与target的大小关系，我们移动left或right指针，以期找到更接近target的和。
关键步骤
排序：首先对整个数组
nums进行升序排序。初始化：初始化一个变量
closestSum用于存储最接近的和。可以将其初始值设为数组前三个元素的和。遍历与固定：用一个
for循环遍历数组，固定第一个数nums[i]。双指针查找： a. 初始化左指针
left = i + 1和右指针right = nums.length - 1。 b. 在left < right的条件下进行循环。 c. 计算当前三数之和currentSum = nums[i] + nums[left] + nums[right]。 d. 更新最接近的和：比较|currentSum - target|和|closestSum - target|的大小。如果当前和更接近target，则更新closestSum = currentSum。 e. 移动指针： i. 如果currentSum < target，说明和偏小，需要增大，将左指针left右移。 ii. 如果currentSum > target，说明和偏大，需要减小，将右指针right左移。 iii. 如果currentSum === target，说明找到了完全匹配的和，直接返回target。返回结果：遍历结束后，
closestSum中存储的就是与target最接近的三数之和。
代码实现
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function (nums, target) {
nums.sort((a, b) => a - b);
// 初始化一个极大的差值和一个结果变量
let minOffset = Infinity, cloestNum = 0;
for (let i = 0; i < nums.length; i++) {
let left = i + 1, right = nums.length - 1;
while (left < right) {
let total = nums[left] + nums[right] + nums[i];
// 如果找到完全匹配，直接返回
if (total === target) {
return target;
}
// 更新最接近的和
if (Math.abs(total - target) < minOffset) {
minOffset = Math.abs(total - target);
cloestNum = total;
}
// 移动指针
if (total < target) {
left++;
} else right--;
}
}
return cloestNum;
};
复杂度分析
时间复杂度：O(n²) 数组排序的时间复杂度为 O(n log n)。
for循环和while循环构成了 O(n²) 的复杂度。总体上，O(n²) 占主导地位。空间复杂度：O(log n) 或 O(n) 不考虑存储结果的数组，空间复杂度主要取决于排序算法所需的栈空间。
相关题目
总结
本题是“三数之和”问题的一个重要变种，考察了在“排序+双指针”框架下，如何从寻找精确值转变为寻找最优近似值。其核心在于维护一个全局最优解，并在遍历过程中不断尝试更新它。