top16
和上一道题很类似，只不过这个是给一个目标值，找三个数，使得他们的和最接近目标值。
解法一 暴力解法
遍历所有的情况，然后求出三个数的和，和目标值进行比较，选取差值最小的即可。本以为时间复杂度太大了，神奇的是，竟然 AC 了。
publicintthreeSumClosest(int[] nums, inttarget) { intsub=Integer.MAX_VALUE; //保存和 target 的差值intsum=0; //保存当前最接近 target 的三个数的和for (inti=0; i<nums.length; i++) { for (intj=i+1; j<nums.length; j++) for (intk=j+1; k<nums.length; k++) { if (Math.abs((nums[i] +nums[j] +nums[k] -target)) <sub) { sum=nums[i] +nums[j] +nums[k]; sub=Math.abs(sum-target); } } } returnsum; }
时间复杂度：O（n³），三层循环。
空间复杂度：O（1），常数个。
解法二
受到上一题的启发，没有看的，推荐大家可以看一下。我们完全可以先将数组排序，然后先固定一个数字，然后利用头尾两个指针进行遍历，降低一个 O（n）的时间复杂度。
如果 sum 大于 target 就减小右指针，反之，就增加左指针。
publicintthreeSumClosest(int[] nums, inttarget) { Arrays.sort(nums); intsub=Integer.MAX_VALUE; intsum=0; for(inti=0;i<nums.length;i++){ intlo=i+1,hi=nums.length-1; while(lo<hi){ if(Math.abs((nums[lo]+nums[hi]+nums[i]-target))<sub){ sum=nums[lo]+nums[hi]+nums[i]; sub=Math.abs(sum-target); } if(nums[lo]+nums[hi]+nums[i]>target){ hi--; }else{ lo++; } } } returnsum; }
时间复杂度：如果是快速排序的 O(log_n)O(logn) 再加上 O（n²），所以就是 O（n²）。
空间复杂度：O（1）。
总
和上一道题非常非常的相似了，先对数组排序，然后利用两头的指针，可以说是十分的优雅了。
