每天一道leetcode(Day 30)

16. 最接近的三数之和

题目描述

给定一个包括  n 个整数的数组  nums  和 一个目标值  target。找出  nums  中的三个整数，使得它们的和与  target  最接近。返回这三个数的和。假定每组输入只存在唯一答案。

示例

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解题思路

• 排序原数组 nums[right] >= nums[left]
• 遍历数组,res = num[i] + nums[left] + nums[right]
• 当 sum - target < res - target 时,res = sum，res 始终记录最小的差值
• 当 sum == target 时
  返回 sum 即为所求
• 当 sum > target,right–
• 当 sum < target,left++

代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
  nums.sort((a, b) => a - b);
  let res = nums[0] + nums[1] + nums[2];
  for (let i = 0; i < nums.length; i++) {
    let left = i + 1,
      right = nums.length - 1;
    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (Math.abs(res - target) > Math.abs(sum - target)) {
        res = sum;
      }
      if (sum > target) right--;
      if (sum < target) left++;
      if (sum === target) return res;
    }
  }
  return res;
};

参考

16. 最接近的三数之和