16. 最接近的三数之和
16. 最接近的三数之和
题目
Given an integer array nums
of length n
and an integer target
, find three integers in nums
such that the sum is closest to target
.
Return the sum of the three integers.
You may assume that each input would have exactly one solution.
Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Example 2:
Input: nums = [0,0,0], target = 1
Output: 0
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).
Constraints:
3 <= nums.length <= 500
-1000 <= nums[i] <= 1000
-10^4 <= target <= 10^4
题目大意
给定一个数组,要求在这个数组中找出 3 个数之和离 target 最近。
解题思路
先对数组进行排序,i 从后往前扫描,这里同样需要注意数组中存在多个重复数字的问题。i 在循环的时候和后一个数进行比较,如果相等,i 继续往前移,直到移到下一个和前一个数字不同的位置。
j,k 两个指针开始一前一后对撞。j 从数组首位开始,k 为 i 的前一个数字,由于经过排序,所以 j < k。对比三个数的和与 target 的大小,小于 target,j 往后移动;大于 target,k 往前移动,逐渐夹逼出最接近 target 的值。
代码
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function (nums, target) {
nums = nums.sort((a, b) => a - b);
const len = nums.length;
let diff = Number.MAX_SAFE_INTEGER;
let res;
for (let i = len - 1; i > 1; i--) {
// 排除 i 重复的情况
if (i === len - 1 || nums[i] !== nums[i + 1]) {
let j = 0;
let k = i - 1;
while (j < k) {
let sum = nums[i] + nums[j] + nums[k];
let minus = Math.abs(sum - target);
if (diff > minus) {
diff = minus;
res = sum;
}
if (sum === target) {
return target;
} else if (sum > target) {
k--;
} else {
j++;
}
}
}
}
return res;
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
15 | 三数之和 | [✓] | 数组 双指针 排序 | |
259 | 较小的三数之和 🔒 | [✓] | 数组 双指针 二分查找 1+ |