4sum.java

public class Solution {
    
    private class Pair{
        
        private int first;
        private int second;
        
        public Pair(int a, int b) {
            first = a;
            second = b;
        }
        
        @Override
        public boolean equals(Object obj) {
            Pair that = (Pair)obj;
            return this.first == that.first && this.second == that.second;
        }
        
        @Override
        public int hashCode(){
            return (first + "" + second).hashCode();
        }
        
        public int getFirst() {
            return this.first;
        }
        
        public int getSecond() {
            return this.second;
        }
        
    }
    public List<List<Integer>> fourSum(int[] num, int target) {
        int len = num.length;
        ArrayList<List<Integer>> res = new ArrayList<List<Integer>>();
        if (len < 4)
            return res;
        HashMap<Integer, ArrayList<Pair>> map = new HashMap<Integer, ArrayList<Pair>>();
        HashSet<ArrayList<Integer>> set = new HashSet<ArrayList<Integer>>();
        Arrays.sort(num);
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                int toFind = target - (num[i] + num[j]);
                if (map.containsKey(toFind)) {
                    ArrayList<Pair> list = map.get(toFind);
                    for (int k = 0; k < list.size(); k++) {
                        ArrayList<Integer> ans = new ArrayList<Integer>();
                        ans.add(num[list.get(k).getFirst()]);
                        ans.add(num[list.get(k).getSecond()]);
                        ans.add(num[i]);
                        ans.add(num[j]);
                        if (!set.contains(ans)) {
                        res.add(ans);
                            set.add(ans);
                        }
                    }
                }
            }
            for (int j = 0; j < i; j++) {
                int sum = num[j] + num[i];
                if (!map.containsKey(sum)) {
                    ArrayList<Pair> temp = new ArrayList<Pair>();
                    temp.add(new Pair(j, i));
                    map.put(sum, temp);
                }
                map.get(sum).add(new Pair(j, i));
            }
        }
        return res;
    }
}