原题地址：最接近的三数之和
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
暴力求解
本题算是上一题 三数之和 的一个变种，所以解法也与上一题类似，依然是暴力解法和双指针法。
暴力解法依然是通过遍历找出所有的三元组，然后求出它们的和，再找出其中与target最接近的即可：
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
const threeSumClosest1 = function(nums, target) {
let [min, result] = [Infinity, Infinity]; // 最小差值及此时的三数之和
let [sum, difference] = [0, 0]; // 三数之和及其与target的差值
for (let i = 0; i < nums.length - 2; i ++) {
for (let j = i + 1; j < nums.length - 1; j ++) {
for (let k = j + 1; k < nums.length; k ++) {
sum = nums[i] + nums[j] + nums[k];
difference = Math.abs( sum - target);
if (difference < min) {
[min, result] = [difference, sum];
if (min === 0) { // 说明已经找到了与target相等的结果，不可能再找到更小的了
return result;
}
}
}
}
}
return result;
};
测试：
let start = new Date();
const test = threeSumClosest1;
console.log(test([-1, 2, 1, -4], 1)); // 2
console.log(test([1, 1, 1, 0], 100)); // 3
console.log(new Date().getTime() - start.getTime()); // 5
时间复杂度： 三重遍历，时间复杂度为O($n^3$)
空间复杂度： 只需要固定大小的额外空间，空间复杂度为O(1)
双指针法
本题也可以采用双指针法，固定一个数，通过双指针找另两个数并求和，再找出与target最接近的和即可：
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
const threeSumClosest2 = function(nums, target) {
nums = nums.sort((a, b) => a - b); // 先排序
let [min, result] = [Infinity, Infinity]; // 最小差值及此时的三数之和
let [sum, difference] = [0, 0]; // 三数之和及其与target的差值
// 固定一个数，找出另两个符合条件的数
for (let i = 0; i < nums.length - 2; i ++) {
// 由于排过序，如果三数之和大于target，则它们的和只会离target越来越远
// 注意要至少找到过一个有效和
if (min < Infinity && nums[i] * 3 > target) {
break;
}
// 双指针，初始分别在两端
let [left, right] = [i + 1, nums.length - 1];
while (left < right) {
sum = nums[left] + nums[right] + nums[i];
if (sum < target) { // 和小于target就让左指针右移
left ++;
} else if (sum > target) { // 和大于target就让右指针左移
right --;
} else {
return sum; // 如果等于，直接返回结果即可
}
difference = Math.abs(target - sum);
if (difference < min) {
[min, result] = [difference, sum]
}
}
}
return result;
};
测试：
let start = new Date();
const test = threeSumClosest2;
console.log(test([-1, 2, 1, -4], 1)); // 2
console.log(test([1, 1, 1, 0], 100)); // 3
console.log(new Date().getTime() - start.getTime()); // 3
时间复杂度： 固定一个数需要一次遍历，双指针需要一次遍历，共两次遍历，时间复杂度为O($n^2$)
空间复杂度： 空间复杂度为O(1)
本文由 李海平 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 28,2019