LeetCode-最接近的三数之和「数组」

[zentan66]

题目

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

[zentan66]

code实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
  let len = nums.length
  // 对数组排序
  nums.sort((a, b) => {
    return a - b
  })
  console.log(nums, '---nums')
  // 初始化的时候 认为前三个数的就是要的结果
  let ans = nums[0] + nums[1] + nums[2]
  for (let i = 0; i < nums.length; i++) {
    // 双指针思想
    let start = i + 1
    let end = nums.length - 1

    while (start < end) {
      let tempSum = nums[i] + nums[start] + nums[end]
      // 最接近，换一句话说就是相减绝对值最小。
      // 在不停地执行while循环的过程中，不断的更新 ans
      if (Math.abs(target - tempSum) < Math.abs(target - ans)) {
        ans = tempSum
      }
      if (tempSum > target) {
        end--
      } else if (tempSum < target) {
        start++
      } else {
        // 正好和target相等 返回ans
        return ans
      }
    }
  }
  return ans
}

思路

遍历+双指针 确定一个元素之后，对该元素后的集合使用双指针，找出最接近target的元素合集 时间复杂度：O(nlogn)+O(n^2)=O(n^2)