Skip to content

Latest commit

 

History

History
70 lines (57 loc) · 1.51 KB

16. 最接近的三数之和.md

File metadata and controls

70 lines (57 loc) · 1.51 KB

16. 最接近的三数之和

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

示例:

输入:nums = [-1,2,1,-4], target = 1
输出:2
解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

提示:

3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

思路

  1. 先排序
  2. 给默认的 result
  3. 遍历+双指针,找到最接近的值。如果是目标值直接返回,否则继续遍历完

代码

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

function getDistance(target, num1, num2) {
  let d1 = Math.abs(target - num1);
  let d2 = Math.abs(target - num2);
  return d1 > d2 ? num2 : num1;
}

复杂度分析

时间复杂度 $O(NlogN)$

空间复杂度 $O(1)$