16. 三数之和最接近

题目

给定一个整数数组 nums 和一个目标数 target，在 nums 中找出三个数，要求其和与 target 最接近。
即 nums[i] + nums[j] + nums[k] + taget ~= 0

解析

1. 暴力找出所有三元结果，依次和 target 比较。

2. 在暴力三次循环的基础上，作出提前终止条件。利用排序数组。
   （1）固定 i j k。
   （2）移动 k 当 和 大于 sum 的时候，可以终止，因为后续的和都比 sum 大。

   
   image.png

image.png

排序后效率明显高一些，但和其他人的提交比仍然很低，而且这里没有空间换取时间，也就是说存在空间换取时间的解法，空间用在哪里？

伪码

sort(nums)
if target < 0
  i = 0,j=i+1,k=j+1
 diff = nums[i] + num[j] +num[k] -target
  if diff > 0 
      rst = sum-target < target-rst ? sum : rst
      return
  rst = sum
      i++ j++ k++
if target > 0 
    i=len(s)-1 j=i-1 k= j-1
    diff = nums[i] + nums[j] + num[k] - target
     if diff < 0 
        rst = target - sum < rst - target ? sum : rst
        return
      rst = sum
     i-- j-- k--

代码