https://leetcode.com/problems/3sum-closest/
【描述】
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).
【中文描述】
给定一个数组n个数字，并且给一个target数，要求从这个数组中找出3个数字，其和最接近这个target。比如上面例子显示的那样。
同时，leetCode很仁慈的说，假定每个数组中只会有一个唯一解。
————————————————————————————————————————————————————————————
【初始思路】
这道题其实和3SUM普通那道题差不多（3SUM下面讨论一下）。 无非就是找最接近target的3元组。那我们完全可以套用3SUM的代码，稍加改动即可。
怎么改？
首先，3SUM的代码其实是把所有3元组全部算出来了。那我们在计算所有3SUM的同时，实时地把最接近的3元组记录下来不就好了。然后在计算结束后，我们返回最接近的这个值不就完了？
此外,low和high的跳跃和3SUM的原则是一样的，如果比target还大,high--，如果比target小，low++. 关于3SUM算法下面会讨论，这种跳跃方法，low和high肯定能计算到所有的数字，不会有漏掉的可能。
【Show me the Code!!!】
public static int threeSumClosest(int[] nums, int target) {
int len = nums.length;
Arrays.sort(nums);
//算出最大可能和 + 最小可能和, 避免最差情况
int max = nums[len - 1] + nums[len - 2] + nums[len - 3];
int min = nums[0] + nums[1] + nums[2];
if(target >= max) return max;
if(target <= min) return min;
int diff = Integer.MAX_VALUE;
int result = 0;
for (int i = 0; i < len; i++) {
int low = i + 1;
int high = len - 1;
while (low < high) {
int sum = nums[i] + nums[low] + nums[high];
if(Math.abs(target-sum) < diff) { //只要比diff小,就更新diff,同时记录三元组和
diff = Math.abs(target-sum);
result = sum;
} else {
if(sum > target) high--;
else low++;
}
}
}
return result;
}
3SumClosest
关于3Sum题的反思和分析
https://leetcode.com/problems/3sum/
题目描述：
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
- Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
- The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
中文描述：
给一个数组，要求找出其中的和为0的三个数字的组合。 要求找出所有，并且，所有3元组都必须升序排列，并且不能有重复。看例子就能看懂。
返回类型根据题目要求是： List<List<Integer>> ， 一个数字列表的列表。
【思路】
先考虑会不会有特殊情况，自己试了几个例子，发现，如果数组为null或者数组元素个数小于3个的时候，统一返回了空list，这些情况可以单独写代码应对。
接下来就考虑一般情况。
对于数组题，结果不要求返回位置相关信息的。最好都先考虑排序一下，然后再计算，会更简单直观，这个题也不例外。先排序一下：Arrays.sort(nums);
排序后呢？
由于根据题意，要求三元组相加和等于0. 那么，可以肯定的是，需要遍历数组，对于每一个数字nums[i]，在余下的数字中找出另外两个数字使其满足加起来=0的条件。
如何在剩余的数组中找到我们想要的两个数字是本题的技巧所在。
最简单的办法是i, j指针2层循环。这是蛮力算法，仔细想想你会发现，其实很多计算都是不必要的。
首先，数组是已经从小到大排序好的，而这两个数之和是个固定值0-nums[i]， 我们可不可以在一次遍历里用两个指针，其和等于0-nums[i]是一种情况， 其和不等于0-nums[i]是另外一种情况，之后移动两个指针进行下一次计算不就可以了么？
两个指针遍历一维数组，首先想到的办法就是两边各放一个，然后往中间靠拢。我们来分析一下可不可行。
假设，两个指针:low和high, low指向i+1(因为nums[i]已经确定了，low应该从i的下一位开始遍历), high指向数组最后一个元素。 两者相加，无非3种可能性：（1）大于target（2）小于target（3）等于target。挨个分析一下：
（1）大于target. 由于数组已经排序好了，在nums[low] + nums[high] > target后，由于我们要对两个指针做微调，让它尽可能达到target值。假设我们调low，low+1。那么由于nums[low+1] > nums[low]，所以low移动后的nums[low] + nums[high] > target 就是必然的了！事实上，这个值比上面那个值还大！所以这个情况下，应该移动high，让high-1。 那么nums[low] + nums[high]就比上面的值稍小一点，靠近了一点target，然后才有可能和target相等；
（2）小于target. 同理，这个时候应该移动low+1，而不是high-1.
（3）如果nums[low] + nums[high] = target。 那么low和high需要各自向里面移动一位。low++，high--。
这样，就能够保证遍历到所有的可能性。
【重复元素！】
题目没有说没有重复元素，我试了几个例子，确实是，如果有重复元素，官方的结果里是去重的。说明可能会有重复元素的用例。
那怎么办呢？上面的办法，如果不加任何实时去重机制，那结果里肯定会有一大堆重复结果。如果我们在结果里去重，就慢得多了。因为首先重复计算了很多结果，最终又得去掉他们，做了无用功。
那我们就考虑如何在上面的机制里实时去重。
还是回到数组已经排序的特性上来，考虑下面的序列：
-3, -1, -1, -1, -1, 0, 1, 1, 1, 4, 4, 5
i low high
当i指向-3的时候，起初low在-1的位置，而high在5的位置，-1+5 > 3，high回退到4。 -1+4 = 3。这个时候成功了，好我们记录下这组结果。记录结束后呢？如何处理？直接low++，high--?
那么low+1又到了-1，而high-1后到了4（如下面序列）， -1+4 =3, 这组结果就肯定被记录下来了。这就出现了重复结果。
-3, -1, -1, -1, -1, 0, 1, 1, 1, 4, 4, 5
i low high
考虑排序数组的特性，由于当low在-1的时候已经计算了一个结果了（-3,-1,4），那么下一个low遇到-1的时候，是不是可以直接跳过？显然，跳过后对结果没有任何影响，因为当前值只要不变，我们想找的另外一个值肯定不会变！而对于high，也应该同步跳过4，因为low已经跳过了-1到达了0，4就绝对不可能是合理的结果了（0+4>3）。所以high也需要跳过4。
可以了么？考虑下面的串：
-3, -3 -1, -1, -1, -1, 0, 1, 1, 1, 4, 4, 5
i low high
当i指向第一个-3的时候，我们势必能计算出一些结果来。等low和high在中间相遇的时候，此轮遍历结束，i++。这个时候i又指向了-3，再计算一遍的话，显然会有重复结果。怎么办？
我们在上面推移low和high的同时，其实可以同步推移i，因为 i 的值对循环内部的算法不产生任何影响，我们直接把指向第一个-3的i指向第二个-3。 相当于忽略掉重复的-3。 这样，本轮循环结束后，i++之后，肯定就会到达下一个新值，而不再重复-3. 这个是可行的
最后，我们看看代码
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if(nums == null || nums.length < 3) return result;
Arrays.sort(nums);
for(int i = 0; i < nums.length; i++){
int low = i+1;
int high = nums.length -1;
while(low < high){
if(nums[i] + nums[low] + nums[high] == 0){
result.add(Arrays.asList(nums[i], nums[low], nums[high]));
while(i + 1 < nums.length && nums[i + 1] == nums[i]) i++;//去重考虑.
while(low + 1 < nums.length && nums[low] == nums[low + 1]) low++;//因为i移动的话,low肯定要移动.最终low肯定停留在i后一位,所以没问题
while(high - 1 >= 0 && nums[high] == nums[high - 1]) high--;//去重考虑
/**
* 去重结束后,low和high往中间汇合
* 并且,在当前low+high = 0 - nums[i]的情况下,low和high是唯一的组合.所以可以同时推移
*/
low++;
high--;
} else if(nums[i] + nums[low] + nums[high] > 0) {
/**
* 不等情况(1)
*/
high--;
} else low++;//不等情况(2)
}
}
return result;
}
3Sum