【015，3|015，3 Sum】给定一个数组S，它包含n个整数，它是否存在3个元素a，b，c，满足a+b+c=0?找出所有满足条件的元素数组。
提示：a，b，c三个元素必须是升序排列（也就是满足a ≤ b ≤ c），最终的结果不能包含重复的元素数组。例如给定S为{-1 0 1 2 -1 -4}，返回结果是(-1, 0, 1)和(-1, -1, 2)。
http://blog.csdn.net/lnho2015/article/details/51314133]
暴力，三次for循环遍历解决问题
http://blog.csdn.net/hcbbt/article/details/44041671
分析：
先排序，再左右夹逼，复杂度 O(n*n)。
N-sum 的题目都可以用夹逼做，复杂度可以降一维。
public class Solution {public List> threeSum(int[] num) {
List> ret = new ArrayList>();
int len = num.length, tar = 0;
if (len <= 2)
returnret;
Arrays.sort(num);
for (int i = 0;
i <= len - 3;
i++) {
// first number : num[i]
int j = i + 1;
// second number
int k = len - 1;
// third number
while (j < k) {
if (num[i] + num[j] + num[k] < tar) {
++j;
} else if (num[i] + num[j] + num[k] > tar) {
--k;
} else {
ret.add(Arrays.asList(num[i], num[j], num[k]));
++j;
--k;
// folowing 3 while can avoid the duplications//保证没有重复元素
while (j < k && num[j] == num[j - 1])
++j;
while (j < k && num[k] == num[k + 1])
--k;
}
}
while (i <= len - 3 && num[i] == num[i + 1])
++i;
}
return ret;
}
}
