3Sum problem

题目如下：

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.
** 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.

解法一：

用递归一个个去组装检测，尝试所以组合。
首先需要把数组排序，然后后面我们才能判断检测相同数字。
然后在递归函数中，我们不断把数字加入subset里面，只要subset的size达到3而且里面的📚加起来等于0，我们就把这个subset加入到输出结果中去。

public class Solution {
    /**
     * @param numbers : Give an array numbers of n integer
     * @return : Find all unique triplets in the array which gives the sum of zero.
     */
    public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {
        // write your code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(numbers);
        
        if( numbers.length == 0 ) {
            return result;
        }
        
        findSets(numbers, result, new ArrayList<Integer>(), 0);
        return result;
    }
    
    public void findSets(int[] numbers, ArrayList<ArrayList<Integer>> result, ArrayList<Integer> subset, int startPoniter){
        if(subset.size() == 3){
            int sum = 0;
            for(int d : subset){
                sum += d;
            }
            if (sum == 0){
                result.add(new ArrayList<Integer>(subset));
            }
            return;
        }
        
        for(int i = startPoniter; i < numbers.length; i++) {
            subset.add(numbers[i]);
            findSets(numbers, result, subset, i+1);
            subset.remove(subset.size() -1);
            while(i < numbers.length-1 && numbers[i] == numbers[i+1]){
                i++;
            }
        }
        
    }
    
    
}

解法二：
设置3个指针，初始化分别指向第一个元素target, 第二个元素left, 最后一个元素right。
当left小于right且，三个数加起来为0时候，我们就把它加入结果中。
当三个数加起来小于0，我们把left++，因为前面我们提过数组是排过序的，所以三个数和小于1，我们就把left往大的移。反之当三个数大于1 时候，我们把right往左移动，以获得更小的数字。

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        if(num.length < 3) return result;
        Arrays.sort(num);
        
        HashSet set = new HashSet();
        for(int i=0; i<num.length-2; i++){
            int target = num[i];
            int left = i+1;
            int right = num.length-1;
            
            while(left<right){
                if(num[left]+num[right]+target==0){
                    ArrayList<Integer> subset = new ArrayList<Integer>();
                    subset.add(target);
                    subset.add(num[left]);
                    subset.add(num[right]);
                    if(set.add(subset))         //check if the set is duplicate
                        result.add(subset);
                        left++;
                        right--;
                          
                }else if(num[left]+num[right]+target<0){
                    left++;
                }else if(num[left]+num[right]+target>0){
                    right--;
                }
            }
        }
        return result;
    }
}