16. 最接近的三数之和
题目描述
输入长度为 n 的整数数组 nums 和整数 target。
从 nums 中选出三个下标不同的数，使它们的和与 target 的差的绝对值尽量小。返回这个和。
题目保证最接近的和只有一个。
示例 1
输入：nums = [-1,2,1,-4], target = 1 输出：2
解释：-1 + 2 + 1 = 2，与 1 相差 1，没有更接近的选法。
示例 2
输入：nums = [0,0,0], target = 1 输出：0
解释：唯一的和是 0。
数据范围
3 <= nums.length <= 1000-1000 <= nums[i] <= 1000-10^4 <= target <= 10^4
解题思路
先排序。外层固定最小的数 nums[i]，在它右边用左右指针 lo、hi 找另外两个数。三数和 s 偏小时，只有把 lo 右移才能让和变大；偏大时只有把 hi 左移才能变小。每算出一个 s 就和当前最优 best 比较离 target 的距离。若 s 恰好等于 target，距离为 0，直接返回。
为什么正确
对固定的 i，被指针跳过的组合都不会比已经见过的和更接近 target：s < target 时，nums[lo] 与 hi 左侧任何数配对的和都不超过 s，只会更远，所以可以放弃 lo。
复杂度分析
排序 O(n log n)，双指针 O(n²)，总时间 O(n²)；空间 O(log n)（排序所需）。
易错点
best 不能初始化为 0 或无穷大后直接做 abs(best - target)，否则可能溢出或返回一个不是三数之和的值；用前三个数之和初始化最稳妥。指针移动方向由 s 与 target 的大小决定，而不是由 best 决定。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
best = nums[0] + nums[1] + nums[2]
for i in range(n - 2):
lo, hi = i + 1, n - 1
while lo < hi:
s = nums[i] + nums[lo] + nums[hi]
if abs(s - target) < abs(best - target):
best = s
if s == target:
return s
if s < target:
lo += 1
else:
hi -= 1
return bestclass Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int best = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n - 2; i++) {
int lo = i + 1, hi = n - 1;
while (lo < hi) {
int s = nums[i] + nums[lo] + nums[hi];
if (Math.abs(s - target) < Math.abs(best - target)) {
best = s;
}
if (s == target) {
return s;
}
if (s < target) {
lo++;
} else {
hi--;
}
}
}
return best;
}
}class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int n = nums.size();
int best = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n - 2; i++) {
int lo = i + 1, hi = n - 1;
while (lo < hi) {
int s = nums[i] + nums[lo] + nums[hi];
if (abs(s - target) < abs(best - target)) {
best = s;
}
if (s == target) {
return s;
}
if (s < target) {
lo++;
} else {
hi--;
}
}
}
return best;
}
};func threeSumClosest(nums []int, target int) int {
sort.Ints(nums)
n := len(nums)
best := nums[0] + nums[1] + nums[2]
abs := func(x int) int { return int(math.Abs(float64(x))) }
for i := 0; i < n-2; i++ {
lo, hi := i+1, n-1
for lo < hi {
s := nums[i] + nums[lo] + nums[hi]
if abs(s-target) < abs(best-target) {
best = s
}
if s == target {
return s
}
if s < target {
lo++
} else {
hi--
}
}
}
return best
}var threeSumClosest = function(nums, target) {
nums.sort((a, b) => a - b);
const n = nums.length;
let best = nums[0] + nums[1] + nums[2];
for (let i = 0; i < n - 2; i++) {
let lo = i + 1, hi = n - 1;
while (lo < hi) {
const s = nums[i] + nums[lo] + nums[hi];
if (Math.abs(s - target) < Math.abs(best - target)) {
best = s;
}
if (s === target) {
return s;
}
if (s < target) {
lo++;
} else {
hi--;
}
}
}
return best;
};function threeSumClosest(nums: number[], target: number): number {
nums.sort((a, b) => a - b);
const n = nums.length;
let best = nums[0] + nums[1] + nums[2];
for (let i = 0; i < n - 2; i++) {
let lo = i + 1, hi = n - 1;
while (lo < hi) {
const s = nums[i] + nums[lo] + nums[hi];
if (Math.abs(s - target) < Math.abs(best - target)) {
best = s;
}
if (s === target) {
return s;
}
if (s < target) {
lo++;
} else {
hi--;
}
}
}
return best;
}