class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
}
};
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
提示：
3 <= nums.length <= 1000-1000 <= nums[i] <= 1000-104 <= target <= 104原站题解
javascript 解法, 执行用时: 72 ms, 内存消耗: 42.9 MB, 提交时间: 2023-07-10 09:12:53
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function (nums, target) {
nums.sort((a, b) => a - b);
const n = nums.length;
let ans = 0;
let minDiff = Number.MAX_SAFE_INTEGER;
for (let i = 0; i < n - 2; i++) {
const x = nums[i];
if (i > 0 && x === nums[i - 1]) {
continue; // 优化三
}
// 优化一
let s = x + nums[i + 1] + nums[i + 2];
if (s > target) { // 后面无论怎么选，选出的三个数的和不会比 s 还小
if (s - target < minDiff) {
ans = s;
}
break;
}
// 优化二
s = x + nums[n - 2] + nums[n - 1];
if (s < target) { // x 加上后面任意两个数都不超过 s，所以下面的双指针就不需要跑了
if (target - s < minDiff) {
minDiff = target - s;
ans = s;
}
continue;
}
// 双指针
let j = i + 1, k = n - 1;
while (j < k) {
s = x + nums[j] + nums[k];
if (s === target) {
return target;
}
if (s > target) {
if (s - target < minDiff) { // s 与 target 更近
minDiff = s - target;
ans = s;
}
k--;
} else { // s < target
if (target - s < minDiff) { // s 与 target 更近
minDiff = target - s;
ans = s;
}
j++;
}
}
}
return ans;
};
golang 解法, 执行用时: 4 ms, 内存消耗: 3 MB, 提交时间: 2023-07-10 09:12:28
func threeSumClosest(nums []int, target int) (ans int) {
sort.Ints(nums)
n := len(nums)
minDiff := math.MaxInt
for i, x := range nums[:n-2] {
if i > 0 && x == nums[i-1] {
continue // 优化三
}
// 优化一
s := x + nums[i+1] + nums[i+2]
if s > target { // 后面无论怎么选，选出的三个数的和不会比 s 还小
if s-target < minDiff {
ans = s
}
break
}
// 优化二
s = x + nums[n-2] + nums[n-1]
if s < target { // x 加上后面任意两个数都不超过 s，所以下面的双指针就不需要跑了
if target-s < minDiff {
minDiff = target - s
ans = s
}
continue
}
// 双指针
j, k := i+1, n-1
for j < k {
s = x + nums[j] + nums[k]
if s == target {
return target
}
if s > target {
if s-target < minDiff { // s 与 target 更近
minDiff = s - target
ans = s
}
k--
} else { // s < target
if target-s < minDiff { // s 与 target 更近
minDiff = target - s
ans = s
}
j++
}
}
}
return ans
}
java 解法, 执行用时: 2 ms, 内存消耗: 42 MB, 提交时间: 2023-07-10 09:12:04
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int ans = 0, n = nums.length;
int minDiff = Integer.MAX_VALUE;
for (int i = 0; i < n - 2; i++) {
int x = nums[i];
if (i > 0 && x == nums[i - 1]) {
continue; // 优化三
}
// 优化一
int s = x + nums[i + 1] + nums[i + 2];
if (s > target) { // 后面无论怎么选，选出的三个数的和不会比 s 还小
if (s - target < minDiff) {
ans = s;
}
break;
}
// 优化二
s = x + nums[n - 2] + nums[n - 1];
if (s < target) { // x 加上后面任意两个数都不超过 s，所以下面的双指针就不需要跑了
if (target - s < minDiff) {
minDiff = target - s;
ans = s;
}
continue;
}
// 双指针
int j = i + 1, k = n - 1;
while (j < k) {
s = x + nums[j] + nums[k];
if (s == target) {
return target;
}
if (s > target) {
if (s - target < minDiff) { // s 与 target 更近
minDiff = s - target;
ans = s;
}
k--;
} else { // s < target
if (target - s < minDiff) { // s 与 target 更近
minDiff = target - s;
ans = s;
}
j++;
}
}
}
return ans;
}
}
python3 解法, 执行用时: 72 ms, 内存消耗: 16.2 MB, 提交时间: 2023-07-10 09:11:32
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
min_diff = inf
for i in range(n - 2):
x = nums[i]
if i and x == nums[i - 1]:
continue # 优化三
# 优化一
s = x + nums[i + 1] + nums[i + 2]
if s > target: # 后面无论怎么选，选出的三个数的和不会比 s 还小
if s - target < min_diff:
ans = s
break
# 优化二
s = x + nums[-2] + nums[-1]
if s < target: # x 加上后面任意两个数都不超过 s，所以下面的双指针就不需要跑了
if target - s < min_diff:
min_diff = target - s
ans = s
continue
# 双指针
j, k = i + 1, n - 1
while j < k:
s = x + nums[j] + nums[k]
if s == target:
return s
if s > target:
if s - target < min_diff: # s 与 target 更近
min_diff = s - target
ans = s
k -= 1
else: # s < target
if target - s < min_diff: # s 与 target 更近
min_diff = target - s
ans = s
j += 1
return ans
python3 解法, 执行用时: 6444 ms, 内存消耗: 15.1 MB, 提交时间: 2022-08-02 15:44:10
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
best = 10**7
# 根据差值的绝对值来更新答案
def update(cur):
nonlocal best
if abs(cur - target) < abs(best - target):
best = cur
# 枚举 a
for i in range(n):
# 保证和上一次枚举的元素不相等
if i > 0 and nums[i] == nums[i - 1]:
continue
# 使用双指针枚举 b 和 c
j, k = i + 1, n - 1
while j < k:
s = nums[i] + nums[j] + nums[k]
# 如果和为 target 直接返回答案
if s == target:
return target
update(s)
if s > target:
# 如果和大于 target，移动 c 对应的指针
k0 = k - 1
# 移动到下一个不相等的元素
while j < k0 and nums[k0] == nums[k]:
k0 -= 1
k = k0
else:
# 如果和小于 target，移动 b 对应的指针
j0 = j + 1
# 移动到下一个不相等的元素
while j0 < k and nums[j0] == nums[j]:
j0 += 1
j = j0
return best