给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
示例:
输入:nums = [-1,2,1,-4], target = 1 输出:2 解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。 提示:
使用排序 + 双指针
方法解决;
如果使用暴力枚举的话时间复杂度会到 O(n3),需要降低时间复杂度
nums[i]
start = i + 1
处,后指针指向end = nums.length - 1
,也就是结尾处sum = nums[i] + nums[start] + nums[end]
结果,判断 sum 与目标 target 的距离,如果距离比当前 result 与目标 target的距离更小,则将sum
更新为result
sum > target
, 则 end--
, 如果 sum < target
, 则 start++
,如果sum === target
,则说明距离为0,直接返回结果/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var threeSumClosest = function(nums, target) {
// 首先进行数组排序,时间复杂度 O(nlogn)
nums.sort((a, b) => a - b);
let result = nums[0] + nums[1] + nums[2];
// 对数组nums进行遍历,每遍历一个值利用其下标 i,形成一个固定值 nums[i]
for(let i = 0; i < nums.length; i++) {
// 前指针指向 start = i + 1处
let start = i + 1;
// 后指针指向 end = nums.length - 1
let end = nums.length - 1;
while(start < end) {
let sum = nums[i] + nums[start] + nums[end];
// 如果sum与target的距离更小,则更新 sum 为result
if(Math.abs(target - sum) < Math.abs(target - result)) {
result = sum;
}
// 如果三数之和大于目标值,则应该找更小的第三个数, 即如果 sum > target, 则 end--
if(sum > target) {
end--;
} else if(sum < target) {
// /如果三数之和小于目标值,则应该找更大的第二个数,即如果 sum < target, 则 start++
start++;
} else {
// 如果当前三数之和等于目标值, 则已找到最佳值,直接返回结果即可
return result;
}
}
}
return result;
};