数据结构与算法之最接近的三数之和

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

提示:

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

示例

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

分析

排序加双指针, 我们假设结果reuslt初始化时为nums[0] + nums[1] + nums[2], 随着指针变换三数相加的结果为temp, 如果temp - target小于result - target则说明temp更接近target, 更新result为temp. 同时判断temp与target的大小, 如果temp大于target则右指针左移, 小于左指针右移,否则返回reuslt

代码

Python3

def threeNumCloset(self, nums, target):
  n = len(nums)
  if not nums or n < 3:
    return None

  nums.sort()
  result = float('inf')

  for i in range(n):
    if i > 0 and nums[i] == nums[i - 1]:
      continue

    left = i + 1
    right = n - 1

    while left < right:
      temp = nums[i] + nums[left] + nums[right]

      if temp == target:
        return target
      if abs(temp - target) < abs(result - target):
        result = temp
      if temp < target:
        left += 1
      else:
        right -= 1

  return result

JavaScript

function threeNumCloset(self, nums, target){
  const n = nums.length
  let result = nums[0] + nums[1] + nums[2]
  if (n < 3 || nums === null ) return null
  nums.sort((a, b) => a - b)

  for (let i = 0; i < n; i++) {
    if (i > 0 && nums[i] == nums[i-1]) continue
    let left = i + 1
    let right = n - 1

    while (left < right) {
      let temp = nums[i] + nums[left] + nums[right]
      if (Math.abs(temp - target) < Math.abs(result - target)) {
        result = temp
      }
      if (temp < target) {
        left++
      } else if (temp > target) {
        right--
      } else {
        return result
      }
    }
  }
  return result
}