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<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        int len = num.length, tar = 0;

        if (len <= 2)
            return  ret;

        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;

    }
}