16. 最接近的三数之和

🟠   🔖  数组 双指针 排序  🔗 力扣 LeetCode

题目

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 最近。

解题思路

• 这一题看似和 第 15 题 和 第 18 题 很像，都是求 3 或者 4 个数之和的问题，也可以使用对撞指针。

• 先对数组进行排序，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+	🟠	🀄️ 🔗