57.3Sum

1.Description(Medium)

Given an array S_of n integers, are there elements a,b, c in S such thata + b + c = 0. Find all unique triplets in the array which gives the sum of zero.

Notice

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.

Example

For example, given array S ={-1 0 1 2 -1 -4}, A solution set is:

(-1, 0, 1)
(-1, -1, 2)

2.Code

Version 1:

经典题目，先排序array，利用a+b=-c，遍历array，使每次的integer = -c，从两头寻找a和b使得a+b=-c。主要难点在于duplicate solution的处理。(因为array里面的值有重复的)此解法复杂度为O(n^2)。

这道题让我们求三数之和，比之前那道要复杂一些，我们还是要首先对原数组进行排序，然后开始遍历排序后的数组，这里注意不是遍历到最后一个停止，而是到倒数第三个就可以了，然后我们还要加上重复就跳过的处理，对于遍历到的数，我们用0减去这个数得到一个sum，我们只需要再之后找到两个数之和等于sum即可，这样一来问题又转化为了求two sum，这时候我们一次扫描，找到了等于sum的两数后，加上当前遍历到的数字，按顺序存入结果中即可，然后还要注意跳过重复数字。题目要求的是a+b+c=0，问题可以推广到a+b+c=target。3sum问题可以转化为2sum问题：对于任意一个A[i]，在数组中的其他数中解2sum问题，目标为target-A[i]。与2sum那题不同，这题要求返回的不是index而是数字本身，并且解不唯一。同时要求解排序并去重。

对排序来说，2sum中的双指针法更为方便，因为算法本身就用到排序。双指针排序法本身会去除一些重复的可能性：

(1, 2, 3, 4), target = 6

在扫描1时，解(2, 3, 4)的2sum = 5问题，找到一个解(1, 2, 3)。

在扫描2时，应当只对后面的数解2sum问题，即对(3, 4)解2sum = 4问题。这样避免再次重复找到解(1, 2, 3)。

但当存在重复数字时，光靠排序仍然无法去重：

(1, 2, 2, 2, 3, 4), target = 9

扫描第一个2时，解(2, 2, 3, 4)中的2sum=7问题，得到解(2, 3, 4)

扫描第二个2时，解(2, 3, 4)中的2sum=7问题，仍然会得到(2, 3, 4)

去除因重复数字而造成重复解有两个办法，

一是将结果存到一个hashset。

而另一种方法就是在扫描数组时跳过重复的数字。上例中，只扫描1, 2, 3, 4来求相应的2sum问题。进一步简化，可以只扫描1, 2。因为3已经是倒数第二个数字，不可能有以它为最小数字的解。

这里注意两次avoid duplicate solution,一次是在选择target的时候，一次是在内循环里面在剩余的array中寻求 2 sum 的解的时候

public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {

       ArrayList<ArrayList<Integer>> result=new ArrayList<>();
        if(numbers==null || numbers.length<3){
            return result;
        }

        Arrays.sort(numbers);
        int len=numbers.length-1;
        //这里i<numbers.length-2是因为只要遍历到倒数第三个值就好了
        for(int i=0;i<numbers.length-2;i++){
            //avoid duplicate solution
            //这里是要么i==0 要么跟前一个数字不同的时候pass
            //或者 if (i != 0 && numbers[i] == numbers[i-1]) continue;
            if(i>0 && numbers[i]!=numbers[i-1]){
                int target=-numbers[i];
                int head=i+1;
                int tail=len;
                while(head<tail){
                    int sum=numbers[head]+numbers[tail];
                    if(sum>target){
                        tail--;
                    }
                    else if(sum<target){
                        head++;
                    }else{
                        ArrayList<Integer> path=new ArrayList<Integer>();
                        path.add(numbers[i]);
                        path.add(numbers[head]);
                        path.add(numbers[tail]);
                        result.add(path);

                        head++;
                        tail--;
                        //avoid duplicate solution,跟unique pair有点相似
                        while(head<tail && numbers[head]==numbers[head-1]){
                            head++;
                        }
                        while(head<tail && numbers[tail]==numbers[tail+1]){
                            tail--;
                        }
                    }
                }
            }           
        }
        return result;       
    }

Version 2: 套用 NSum 模板