题目描述
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
解法
解法一（暴力解法）
思路：使用三层遍历，找到使三元素之和与目标值最接近的结果。
var threeSumClosest = function(nums, target) {
let min_diff;
let result;
for (let i = 0; i < nums.length; i++) {
const a = nums[i];
for (let j = i + 1; j < nums.length; j++) {
const b = nums[j];
for (let k = j + 1; k < nums.length; k++) {
const c = nums[k];
const sum = a + b + c;
if (min_diff == undefined || Math.abs(target - sum) < min_diff) {
min_diff = Math.abs(target - sum);
result = sum;
}
}
}
}
return result;
};
解法二
思路：与求三数之和思想类似，都使用了双指针法。
- 对元素进行排序
- 给定3个指针 i,l,r， 遍历 i，然后在剩余的元素里，同时从 左（
指针l）、右（指针r）两边搜索，找到使与目标值差值最小的组合。
var threeSumClosest = function(nums, target) {
let result;
let min_diff;
// 排序
nums.sort((a, b) => a-b);
for (let i = 0; i < nums.length; i++) {
// 跳过相同值
if (i !==0 && nums[i] == nums[i - 1]) continue;
let l = i + 1;
let r = nums.length - 1;
while (l < r) {
const sum = nums[i] + nums[l] + nums[r];
if (min_diff == null || Math.abs(target - sum) < min_diff) {
min_diff = Math.abs(target - sum);
result = sum;
}
// 若与目标值相同，则差值最小，返回结果
if (sum === target) {
return sum;
// 若大于目标值，则调整右边元素，调小元素
} else if (sum > target) {
r--;
// 若小于目标值，则调整左边元素，调大元素
} else {
l++;
}
}
}
return result;
};
下图是两种方法的执行时间，可以看到第二种方法远远快于第一种。
执行结果
