LeetCoder - 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

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

public class Solution {
    public List<List<Integer>> fourSum(int[] num, int target) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if(num==null || num.length==0) {
            return ret;
        }
        Arrays.sort(num);
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0;i<num.length;i++) {
            map.put(num[i], i);           
        }
        for(int i=0;i<num.length;i++) {
            if(i!=0 && num[i]==num[i-1]) continue;
            for(int j=i+1;j<num.length;j++) {
                if(j!=i+1 && num[j]==num[j-1]) continue;
                for(int m=j+1;m<num.length;m++) {
                    if(m!=j+1 && num[m]==num[m-1]) continue;
                    int n = target - num[i] - num[j] - num[m];
                    Integer idx = map.get(n);
                    if(idx!=null && idx.intValue() > m) {
                        List<Integer> tup = new ArrayList<Integer>();
                        tup.add(num[i]);
                        tup.add(num[j]);
                        tup.add(num[m]);
                        tup.add(n);
                        ret.add(tup);
                    }
                }
            }
        }
        return ret;
    }
}

public class Solution {
    public ArrayList<ArrayList<Integer>> fourSum(int[] num, int target) {
        ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
        HashMap<Integer, ArrayList<int[]>> sum2 = new HashMap<Integer, ArrayList<int[]>>();
        for(int i=0;i<num.length;i++) {
            for(int j=i+1;j<num.length;j++) {
                int sum = num[i] + num[j];
                int[] idxes = new int[2];
                idxes[0] = i;
                idxes[1] = j;
                ArrayList<int[]> idxx = sum2.get(sum);
                if(idxx==null) {
                    idxx = new ArrayList<int[]>();
                    sum2.put(sum, idxx);
                }
                idxx.add(idxes);
            }
        }
        HashSet<String> keys = new HashSet<String>();
        for(Integer s1 : sum2.keySet()) {
            ArrayList<int[]> idx2 = sum2.get(target-s1);
            if(idx2!=null) {
                ArrayList<int[]> idx1 = sum2.get(s1);
                for(int[] i1 : idx1) {
                    for(int[] i2 : idx2) {
                        if(i1[0]!=i2[0] && i1[0]!=i2[1] && i1[1]!=i2[0] && i1[1]!=i2[1]) {
                            ArrayList<Integer> tuple = new ArrayList<Integer>();
                            tuple.add(num[i1[0]]);
                            tuple.add(num[i1[1]]);
                            tuple.add(num[i2[0]]);
                            tuple.add(num[i2[1]]);
                            Collections.sort(tuple);
                            String key = tuple.get(0) + "_" + tuple.get(1) + "_" + tuple.get(2) + "_" + tuple.get(3);
                            if(!keys.contains(key)) {
                                keys.add(key);
                                ret.add(tuple);
                            }
                        }
                    }
                }
            }
        }
        return ret;
    }
}

==========

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