Another Java Solution using HashMap of 2Sums (still have room to improve efficiency)


  • 1

    General idea is to generate all pairs, then hash all the pairs with sum as the key and pair list as value.
    Then for this new pair list, hash (target - pair's sum) -> can find the other pair.

    But note that not all pairs are valid (e.g. some pairs share same index, and duplicates, etc.), so needs to do some checks and pruning.

    This is a very Object-oriented solution which is easy to understand, but there are lots of room for improvement.

    The overall complexity is O(n^2), but in practice may not be faster than the standard O(n^3) solution.

    public class Solution {
        
        public class Pair {
            int[] i;
            int[] val;
            int sum;
            public Pair(int i1,int val1,int i2,int val2) {
                i = new int[2];
                val = new int[2];
                i[0] = i1;
                i[1] = i2;
                val[0] = val1;
                val[1] = val2;
                sum = val1 + val2;
            }
        }
        
        public boolean canMerge(Pair p1, Pair p2) {
            for(int i=0; i<2; i++)
                for(int j=0; j<2; j++)
                    if (p1.i[i] == p2.i[j])
                        return false;
            return true;
        }
        
        public class Quadruplet {
            int[] a;
            public String hashStr() {
                StringBuilder sb = new StringBuilder();
                for (int i=0; i<a.length; i++)
                    sb.append(a[i]).append("-");
                return sb.toString();
            }
            public ArrayList<Integer> getArrLst() {
                ArrayList<Integer> l = new ArrayList<Integer>(4);
                for(int i : a)
                    l.add(i);
                return l;
            }
        }
        
        public Quadruplet merge(Pair p1, Pair p2) {
            Quadruplet q = new Quadruplet();
            q.a = new int[4];
            q.a[0] = p1.val[0];
            q.a[1] = p1.val[1];
            q.a[2] = p2.val[0];
            q.a[3] = p2.val[1];
            Arrays.sort(q.a);
            return q;
        }
        
        public List<List<Integer>> fourSum(int[] nums, int target) {
            List<List<Integer>> l = new ArrayList<List<Integer>>();
            int n = nums.length;
            Pair[] pairs = new Pair[n*(n-1)/2];
            int count = 0;
            for(int i=0; i<n; i++)
                for (int j=i+1; j<n; j++)
                    pairs[count++] = new Pair(i,nums[i],j,nums[j]);
            Map<Integer,ArrayList<Pair>> map = new HashMap<Integer,ArrayList<Pair>>();
            for(Pair p : pairs) {
                if(map.containsKey(p.sum))
                    map.get(p.sum).add(p);
                else {
                    ArrayList<Pair> pairLs = new ArrayList<Pair>();
                    pairLs.add(p);
                    map.put(p.sum,pairLs);
                }
            }
            Set<String> set = new HashSet<String>();
            for(Pair p : pairs) {
                if(map.containsKey(target-p.sum)) {
                    ArrayList<Pair> ps = map.get(target-p.sum);
                    for(Pair p2 : ps) {
                        if (canMerge(p,p2)) {
                            Quadruplet q = merge(p,p2);
                            if (!set.contains(q.hashStr())) {
                                l.add(q.getArrLst());
                                set.add(q.hashStr());
                            }
                        }
                    }
                }
            }
            return l;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.