Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).这是我被先验知识误导的最深的题，没有之一！！！！！ 经验题是3Sum，可以参考我之前的博文，看看我入坑的基础。
题目分析：在一组数据中寻找三元组，三元组的和要最接近给定的target，最后输出最接近的三元组的和。
题目解法（和3Sum超级类似）：
（1）3Sum例子得到的灵感：观察例子给出的解，每组解中的数字都是升序且无重复数据，所以输出时必须注意。而且怀疑在搜索时是不是数组已经是升序排列。
（2）所以，第一步将所给的数组排序为自然升序。
（3）开始搜索：先确定每组输出元素的第一个nums[i]，也就是最小的一个。如果在该元素左侧开始进行搜索来匹配三元组的话，假设可以匹配到a形成三元组（a,nums[i],x），那么在i指向a时，也会形成三元组（a,nums[i],x）。所以下面将在nums[i]的右侧进行搜索。
（4）使用常见的双端搜索法，进行搜索（可以参考LeetCode中Container With Most Water和我的相关博文），来达到O（n）的时间复杂度。
（5）搜索内循环的解释详细见注释
import java.util.Arrays; public class Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums);//将数组排序 int i=0,closet=0,difference=Integer.MAX_VALUE,temp=0; //closet保存目前最接近target的三元组的和，difference保存三元组的和与target的最小差 for(i=0;i<nums.length;i++){ if(i==0 || (i>0 && nums[i]!=nums[i-1])){ //当i=0时直接开始搜索，i>0时则要检查i指向的左侧相邻元素是否与其相等，若相等，因为相当于已经搜索过了，则此轮搜索跳过 int lower=i+1,high=nums.length-1; //将搜索低位置为i+1,高位为length-1 while(lower<high){ temp=nums[i]+nums[lower]+nums[high]; if(temp==target){ //若三元组的和和target相等，则直接返回 return temp; }else if(Math.abs(temp-target)<difference){ //否则看此时的差值是否优于difference,若优则更新 closet=temp; difference=Math.abs(temp-target); } if(temp<target)lower++; //除过temp==target的情况直接return，其他的情况都要动态更新lower和high，此处的结构和3Sum中不能相同，要特别注意 //这里这么个写法是有学问的，如果发现tofit较大，那么nums[lower]+nums[high]要往大了走：（1）high++，这样很有可能搜出重复解（2）lower++，很安全啊 else high--; } } } return closet; } }
附AC图，开心O(∩_∩)O~~
