题目描述（中等难度）

和上一道题很类似，只不过这个是给一个目标值，找三个数，使得他们的和最接近目标值。

解法一 暴力解法

遍历所有的情况，然后求出三个数的和，和目标值进行比较，选取差值最小的即可。本以为时间复杂度太大了，神奇的是，竟然 AC 了。

时间复杂度：O（n³），三层循环。

空间复杂度：O（1），常数个。

解法二

如果 sum 大于 target 就减小右指针，反之，就增加左指针。

  2.     Arrays.sort(nums);
  3.     int sub=Integer.MAX_VALUE;
  4.     int sum=0;
  5.         int lo=i+1,hi=nums.length-1;
  7.             if(Math.abs((nums[lo]+nums[hi]+nums[i]-target))<sub){
  8.                 sum=nums[lo]+nums[hi]+nums[i];
  9.                 sub=Math.abs(sum-target);
  10.             }
  11.             if(nums[lo]+nums[hi]+nums[i]>target){
  12.             }else{
  13.                 lo++;
  14.             }
  15.         }
  16.     }
  18. }

时间复杂度：如果是快速排序的

再加上 O（n²），所以就是 O（n²）。

总

和上一道题非常非常的相似了，先对数组排序，然后利用两头的指针，可以说是十分的优雅了。

windliang wechat

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^