最接近三数之和

介绍及经验

双指针问题：最接近三数之和

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

示例：

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

经验：

数组的最后一项：arr[arr.length - 1]。倒数第二项：arr[arr.length - 2]。倒数第三项：arr[arr.length - 3]。

所以要找到数组倒数第 x 项，直接通过 arr[arr.length - x] 就可以获取到。

代码

function closestSum (_nums: number[], target: number) {
  // 注意：要先将数组按升序排序，否则下面的判断会失去意义
  const nums = _nums.slice()
  nums.sort((a,b) => a - b)
  // 什么时候需要定义一个变量在循环外面呢？因为每次循环的作用域都不相同，  
  let minDiff = Infinity
  let res
  for (let index = 0; index <= nums.length - 3; index ++) {
    let left = index + 1
    let right = nums.length - 1

    while(left < right) {
      const sum = nums[index] + nums[left] + nums[right]
      const diff = Math.abs(sum - target)

      // 差值为 0，肯定最小，直接返回 sum
      if(diff === 0) {
        return sum
      }
      // 以下情况都是差值不为 0
      if(diff < minDiff) {
        minDiff = diff
        res = sum
      }
      // 如果和小于目标，左指针就右移；否则右指针左移
      if(sum < target) {
        left ++
      } else if(sum > target) {
        right --
      }
    }
  }
  return res
}

// in-source test suites
if (import.meta.vitest) {
  const { it, expect } = import.meta.vitest
  
  it('test intersection 0', () => {
    const nums = [-1,2,1,-4]
    const target = 1
    expect(closestSum(nums, target)).toBe(2)
  })

  it('test intersection 1', () => {
    const nums = [0, 1, 2]
    const target = 1
    expect(closestSum(nums, target)).toBe(3)
  })

  it('test intersection 2', () => {
    const nums = [0, 1, 2, 5, 6, 7, 9]
    const target = 7
    expect(closestSum(nums, target)).toBe(7)
  })
}

LeetCode 链接

https://leetcode.cn/problems/3sum-closest/

最接近三数之和 ​

介绍及经验 ​

代码 ​

LeetCode 链接 ​

最接近三数之和

介绍及经验

代码

LeetCode 链接