3Sum

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.

Note:

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

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

solution :
Brute-force: select 3 elements out of n. It cost O(n^3).
N-Sum question. 
Sort the array. 
For each element a, use two pointers b and c. b starts from a+1, goes from left to right. c starts at the end, goes from right to left. 
If b+c > target, c--;
If b+c < target, b++; 
Thus, for each element, we only need O(n). Overall time complexity can be reduced to O(n^2).
Tips: skip duplicates.

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        int len = num.length;
        for(int i = 0; i <= len - 3; i++){
            if(i != 0 && num[i] == num[i-1]) continue;
            helper(i,i+1,len-1,num,ret);
        }
        return ret;
    }
    public void helper(int first, int second, int third, int[] num, ArrayList<ArrayList<Integer>> ret){
        while(second < third){
            int sum = num[first] + num[second] + num[third];
            if(sum == 0){
                ArrayList<Integer> tmp = new ArrayList<Integer>();
                tmp.add(num[first]);
                tmp.add(num[second]);
                tmp.add(num[third]);
                ret.add(new ArrayList<Integer>(tmp));
                second++;
                third--;
                while(second < third && num[second] == num[second-1]) second++;
                while(second < third && num[third] == num[third+1]) third--;
            }
            else if(sum < 0) second++;
            else third--;
        }
    }
}