4 Sum

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.

Example :
Given array S = {1 0 -1 0 -2 2}, and target = 0
A solution set is:

    (-2, -1, 1, 2)
    (-2,  0, 0, 2)
    (-1,  0, 0, 1)

Also make sure that the solution set is lexicographically sorted.
Solution[i] < Solution[j] iff Solution[i][0] < Solution[j][0] OR (Solution[i][0] == Solution[j][0] AND ... Solution[i][k] < Solution[j][k])

Solution:

Time: O(n^2)
Space: O(n^2)

public class Solution {
    static class Pair{
        int i;
        int j;

        Pair(int i, int j) {
            this.i = i;
            this.j = j;
        }
        
        @Override
        public int hashCode() {
            int hash = 17;
            hash = 31 * hash + this.i;
            hash = 31 * hash + this.j;
            return hash;
        }
        
        @Override
        public boolean equals(Object o) {
            Pair p = (Pair) o;
            return this.i == p.i && this.j == p.j;
        }
    }

    public ArrayList<ArrayList<Integer>> fourSum(ArrayList<Integer> A, int B) {
        Collections.sort(A);
        Map<Integer, Set<Pair>> map = new HashMap<>();
        Set<ArrayList<Integer>> result = new HashSet<>();
        for (int j = 1; j < A.size(); j ++) {
            for (int i = 0; i < j; i ++) {
                int ij = A.get(i) + A.get(j);
                int target = B - ij;
                if (map.containsKey(target)) {
                    Set<Pair> other = map.get(target);
                    for (Pair p : other) {
                        if (p.j < i) {
                            ArrayList<Integer> list = new ArrayList<>();
                            list.add(A.get(p.i));
                            list.add(A.get(p.j));
                            list.add(A.get(i));
                            list.add(A.get(j));
                            result.add(list);
                        }
                    }
                }
                Set<Pair> pairs = map.getOrDefault(ij, new HashSet<Pair>());
                pairs.add(new Pair(i, j));
                map.put(ij, pairs);
            }
        }
        ArrayList<ArrayList<Integer>> r = new ArrayList<>(result);
        Collections.sort(r, new Comparator<ArrayList<Integer>>(){
            @Override
            public int compare(ArrayList<Integer> A, ArrayList<Integer> B) {
                int i = 0;
                int j = 0;
                while (i < A.size() && j < B.size()) {
                    if (A.get(i) < B.get(j)) {
                        return -1;
                    } else if (A.get(i) > B.get(j)) {
                        return 1;
                    } else {
                        i ++;
                        j ++;
                    }
                }
                return 0;
            }
        });
        return r;
    }
}