LeetCoder - 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)

public class Solution {
    public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if(num==null || num.length<=2) {
            return ret;
        }
        Arrays.sort(num);
        int[] list = num;
        HashMap<Integer, HashSet<Integer>> map = new HashMap<Integer, HashSet<Integer>>();
        for(int i=0;i<list.length;i++) {
            int n = list[i];
            HashSet<Integer> set = map.get(n);
            if(set==null) {
                set = new HashSet<Integer>();
                map.put(n, set);
            }
            set.add(i);
        }
        for(int i=0;i<list.length;i++) {
            if(list[i]>0 || (i!=0&&list[i]==list[i-1])) {
                continue;
            }
            for(int j=i+1;j<list.length;j++) {
                if(j!=i+1 && list[j]==list[j-1]) {
                    continue;
                }               
                int target = 0 - list[i] - list[j];
                if(target<list[j]) {
                    break;
                }
                HashSet<Integer> set = map.get(target);
                if(set!=null) {
                    for(Integer idx : set) {
                        if(idx>j) {
                            ArrayList<Integer> tuple = new ArrayList<Integer>();
                            tuple.add(list[i]);
                            tuple.add(list[j]);
                            tuple.add(target);
                            ret.add(tuple);
                            break;
                        }
                    }
                }
            }
        }
        return ret;
    }
}

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        for(int i=0;i<num.length;i++) {
            ArrayList<Integer> set = map.get(num[i]);
            if(set==null) {
                set = new ArrayList<Integer>();
                map.put(num[i], set);
            }
            set.add(i);
        }
        ArrayList<ArrayList<Integer>> rst = new ArrayList<ArrayList<Integer>>();
        HashSet<String> rs = new HashSet<String>();
        HashSet<Integer> cache = new HashSet<Integer>();
        for(int i=0;i<num.length;i++) {
            int a = num[i];
            if(cache.contains(a)) {
                continue;
            }
            HashSet<Integer> cache2 = new HashSet<Integer>();
            for(int j = i+1;j<num.length;j++) {
                int b = num[j];
                if(cache2.contains(b)) {
                    continue;
                }
                int c = 0 - a - b;
                ArrayList<Integer> lst = map.get(c);
                if(lst!=null && lst.get(lst.size()-1)>j) {
                    ArrayList<Integer> tuple = new ArrayList<Integer>();
                    tuple.add(a);
                    tuple.add(b);
                    tuple.add(c);
                    Collections.sort(tuple);
                    String key = tuple.get(0) + "_" + tuple.get(1) + "_" + tuple.get(2);
                    if(!rs.contains(key)) {
                        rst.add(tuple);
                        rs.add(key);
                    }
                    cache.add(a);
                    cache2.add(b);
                }
            }
        }
        return rst;
    }
}

========

public class Solution {
    public List<List<Integer>> threeSum(int[] num) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(num);
        helper(num, 0, 0, new ArrayList<Integer>(), res);
        return res;
    }
    
    private void helper(int[] num, int cur, int curSum, List<Integer> curList, List<List<Integer>> res) {
        if (curList.size() == 3 && curSum == 0) {
            List<Integer> newList = new ArrayList<Integer>(curList);
            res.add(newList);
        } else if (curList.size() < 3) {
            for (int i = cur; i < num.length; i++) {
                int n = num[i];
                curList.add(n);
                helper(num, i + 1, curSum + n, curList, res);
                curList.remove(curList.size() - 1);
                while (i != num.length - 1 && num[i] == num[i + 1]) {
                    i++;
                }
            }
        }
    }
}

=========

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (nums == null || nums.length < 3) {
            return res;
        }
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int target = -1 * nums[i];
            int s = i + 1;
            int e = nums.length - 1;
            while (s < e) {
                int sum = nums[s] + nums[e];
                if (sum == target) {
                    List<Integer> list = new ArrayList<Integer>();
                    list.add(nums[i]);
                    list.add(nums[s]);
                    list.add(nums[e]);
                    res.add(list);
                    while (s < e && nums[s] == nums[s + 1]) {
                        s++;
                    }
                    while (s < e && nums[e] == nums[e - 1]) {
                        e--;
                    }
                    s++;
                    e--;
                } else if (sum < target) {
                    s++;
                } else {
                    e--;
                }
            }
        }
        return res;
    }
}