15 3 Sum

Given an arraySofnintegers, are there elementsa,b,cinSsuch thata+b+c= 0? Find all unique triplets in the array which gives the sum of zero.

Note: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]
]

这是2 sum的延伸，还是用2 pointer来解决。O(n^2)

public ArrayList<ArrayList<Integer>> threeSum(int[] numbers) {
    if (numbers == null || numbers.length == 0 || numbers.length < 3){
        return null;
    }

    Arrays.sort(numbers);// sort 1st
    ArrayList<ArrayList<Integer>> result = new ArrayList<>();
    int len = numbers.length;
    // remmeber to end when we were at the 3rd last element 
    // n sum - 1, 3 sum so, 2
    for(int i = 0; i< len - 2;i++){ 
        //skip duplicate here
       if(i!=0 && numbers[i] == numbers[i-1]){
            continue;
        }
        int cur = numbers[i];
        int left = i+1;
        int right = len - 1;
        while(left < right){
            int sum = cur + numbers[left] + numbers[right];
            if(sum == 0 ){
                ArrayList<Integer> temp = new ArrayList<Integer>();
                temp.add(cur);
                temp.add(numbers[left]);
                temp.add(numbers[right]);
                left++;
                right--;
                //and here
                while(left<right&&numbers[left] == numbers[left-1]){
                    left++;
                }
                //and here
                while(left<right&&numbers[right] == numbers[right+1]){
                    right--;
                }
                result.add(temp);

            } else if(sum > 0){
                right--;
            }else{
                left++;
            }

        }
    }
    return result;
}