给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

思路

  1. 与 《三数之和》 类似
  2. 先排序，i 从小到大遍历，对应的 j、k 由两端往中间移动，时间复杂度 O(n^2)
  3. 若找到目标解，输出 target，否则记录差值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var threeSumClosest = function (nums, target) {
  nums.sort((a, b) => a - b)
  let minGap = Number.MAX_SAFE_INTEGER
  let curResult = 0
  for (let i = 0; i < nums.length - 2; ++i) {
    const iVal = nums[i]
    if (i > 0 && nums[i - 1] === iVal) {
      continue
    }
    let j = i + 1
    let k = nums.length - 1
    while (j < k) {
      const jVal = nums[j]
      const kVal = nums[k]
      const sum = iVal + jVal + kVal
      const gap = Math.abs(sum - target)
      if (gap === 0) {
        return target
      }
      if (gap < minGap) {
        minGap = gap
        curResult = sum
      }
      if (sum < target) {
        ++j
      } else {
        --k
      }
    }
  }
  return curResult
}