📑 题目：16. 最接近的三数之和

🚀 本题 LeetCode 传送门

题目大意

给定一个数组，要求在这个数组中找出 3 个数之和离 target 最近。

解题思路

这一题看似和第 15 题和第 18 题很像，都是求 3 或者 4 个数之和的问题，但是这一题的做法和 15，18 题完全不同。

这一题的解法是用两个指针夹逼的方法。先对数组进行排序，i 从头开始往后面扫。这里同样需要注意数组中存在多个重复数字的问题。具体处理方法很多，可以用 map 计数去重。这里笔者简单的处理，i 在循环的时候和前一个数进行比较，如果相等，i 继续往后移，直到移到下一个和前一个数字不同的位置。j，k 两个指针开始一前一后夹逼。j 为 i 的下一个数字，k 为数组最后一个数字，由于经过排序，所以 k 的数字最大。j 往后移动，k 往前移动，逐渐夹逼出最接近 target 的值。

这道题还可以用暴力解法，三层循环找到距离 target 最近的组合。具体见代码。

代码

package leetcode
import (
 ""math""
 ""sort""
)
// 解法一 O(n^2)
func threeSumClosest(nums []int, target int) int {
 n, res, diff := len(nums), 0, math.MaxInt32
 if n > 2 {
  sort.Ints(nums)
  for i := 0; i < n-2; i++ {
   if i > 0 && nums[i] == nums[i-1] {
    continue
   }
   for j, k := i+1, n-1; j < k; {
    sum := nums[i] + nums[j] + nums[k]
    if abs(sum-target) < diff {
     res, diff = sum, abs(sum-target)
    }
    if sum == target {
     return res
    } else if sum > target {
     k--
    } else {
     j++
    }
   }
  }
 }
 return res
}
// 解法二 暴力解法 O(n^3)
func threeSumClosest1(nums []int, target int) int {
 res, difference := 0, math.MaxInt16
 for i := 0; i < len(nums); i++ {
  for j := i + 1; j < len(nums); j++ {
   for k := j + 1; k < len(nums); k++ {
    if abs(nums[i]+nums[j]+nums[k]-target) < difference {
     difference = abs(nums[i] + nums[j] + nums[k] - target)
     res = nums[i] + nums[j] + nums[k]
    }
   }
  }
 }
 return res
}
func abs(a int) int {
 if a > 0 {
  return a
 }
 return -a
}