0016. 3Sum Closest¶
题目信息¶
- 题号:
最接近的三数之和
- 难度:
Medium
- 主题:
数组、排序、双指针
- 原题:
- 重点:
固定一个数后,用有序和值与目标的大小关系排除一整组数对,并持续保存距离最小的和值
题目重述¶
给定整数数组 nums 和整数 target,选择三个不同下标,返回与 target 最接近的三数之和。
接近程度由 abs(sum - target) 衡量。题目保证最近和值唯一。返回的是三数之和本身,不是下标、三元组或
最小距离。
数组长度位于 [3, 500],元素位于 [-1000, 1000],target 位于 [-10^4, 10^4]。
三数之和与距离都可以由 32 位有符号整数安全保存。
自建示例¶
无法精确命中:
nums = [-5, -1, 2, 6, 9]、target = 4,最近和值为3;精确命中:
nums = [7, -2, 4, 1]、target = 6,三元组[-2, 1, 7]的和为6;全部为负:
nums = [-8, -5, -3, -1]、target = -10,最近和值为-9;目标远大于全部和值:
nums = [1, 2, 5, 8]、target = 100,最大三数之和15最近;最小规模:
nums = [-3, 2, 7]、target = 1,唯一三数之和为6。
C++ 实现¶
#include <algorithm>
#include <cstdlib>
#include <vector>
class Solution {
private:
int enumerateTriples(const std::vector<int>& nums, int target) {
int best = nums[0] + nums[1] + nums[2];
const int n = static_cast<int>(nums.size());
for (int first = 0; first < n; ++first) {
for (int second = first + 1; second < n; ++second) {
for (int third = second + 1; third < n; ++third) {
const int sum = nums[first] + nums[second] + nums[third];
if (std::abs(sum - target) < std::abs(best - target)) {
best = sum;
}
}
}
}
return best;
}
int sortAndTwoPointers(std::vector<int> nums, int target) {
std::sort(nums.begin(), nums.end());
int best = nums[0] + nums[1] + nums[2];
const int n = static_cast<int>(nums.size());
for (int first = 0; first + 2 < n; ++first) {
int left = first + 1;
int right = n - 1;
while (left < right) {
const int sum = nums[first] + nums[left] + nums[right];
if (std::abs(sum - target) < std::abs(best - target)) {
best = sum;
}
if (sum < target) {
++left;
} else if (sum > target) {
--right;
} else {
return target;
}
}
}
return best;
}
public:
int threeSumClosest(std::vector<int>& nums, int target) {
return sortAndTwoPointers(nums, target);
}
};
题解¶
三重枚举¶
三个递增下标共有 O(n³) 种组合。enumerateTriples 逐个计算和值,并在当前距离严格更小时替换
best。题目保证最近和值唯一,所以不需要定义距离相等时的额外选择规则。
暴力法已经给出完整答案条件:算法不必保存三元组,只需维护“目前距离目标最近的和值”。需要优化的是候选组合 数量,而不是答案状态。
固定首值¶
数组排序后固定 nums[first],剩余问题是在有序后缀中选择两个数,使
nums[left] + nums[right] 尽量接近 target - nums[first]。
令 left = first + 1、right = n - 1。在固定 first 时:
右移
left,和值不会减小;左移
right,和值不会增大。
和值相对于目标的位置因此直接决定了唯一有意义的移动方向。
和值偏小¶
若当前 sum < target,固定 first 和 left,再选择任意更小的右端 k < right,有:
nums[first] + nums[left] + nums[k] <= sum < target。
这些和值都位于目标左侧,并且不大于已经检查的 sum,所以它们到目标的距离不会更小。当前候选记录后,
所有使用当前 left 与更小右端的组合都可以排除,只需右移 left,尝试把和值提高。
和值偏大¶
若当前 sum > target,固定 first 和 right,再选择任意更大的左端 k > left,有:
nums[first] + nums[k] + nums[right] >= sum > target。
这些和值都位于目标右侧,并且不小于已经检查的 sum,同样不可能更接近目标。于是可以排除当前
right 与所有更大左端组成的组合,并左移 right,尝试降低和值。
更新顺序¶
当前和值无论偏小还是偏大,都可能是全局最近答案。因此每轮必须先比较
abs(sum - target) 与 abs(best - target),再移动指针。
指针移动的证明依赖“当前边界和值已经记录”:被排除的组合不会优于当前和值,而当前和值本身已经进入
best 的比较。若先移动,可能永久跳过这一边界候选。
搜索不变量¶
固定 first 后,每轮开始时,尚未检查且仍可能优于 best 的数对都位于闭区间 [left, right] 中。
每轮先记录当前边界数对,再依据单调性删除一整组不可能更优的组合。指针相遇时,该首值对应的全部潜在更优
数对都已检查或被支配。外层遍历所有 first 后,best 就是全局最近和值。
精确命中¶
当 sum == target 时,距离为 0。绝对距离不可能小于零,因此当前和值已经达到理论最优,可以立即返回
target。
代码演进¶
enumerateTriples 使用三层循环显式选择三个下标,每个候选独立比较距离。
sortAndTwoPointers 固定首值后,用排序建立和值的单调变化。第三层枚举被两个只向中间移动的指针替代;
一次比较即可排除当前左端或右端参与的一整组候选。
公开入口采用 sortAndTwoPointers。它接收输入副本进行排序,不会改变调用者传入的数组。
复杂度分析¶
方法 |
时间复杂度 |
工作空间 |
主要代价 |
|---|---|---|---|
三重枚举 |
|
|
检查全部三下标组合 |
排序双指针 |
|
|
排序副本后,每个首值执行一次线性双指针扫描 |
排序耗时 O(n log n),被 O(n²) 的双指针阶段主导。工作空间中的 O(n) 来自输入副本;不计返回值。