Share my O(N^2) solution using HashMap


  • 0
    public class Solution {
        public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
            if(A.length==0) return 0;
            Map<Integer, Integer> map1 = new HashMap<>();
            Map<Integer, Integer> map2 = new HashMap<>();
            for(int i=0;i<A.length;i++){
                for(int j=0;j<B.length;j++){
                    int sum = A[i]+B[j];
                    if(!map1.containsKey(sum)) map1.put(sum, 0);
                    map1.put(sum, map1.get(sum)+1);
                    sum = C[i]+D[j];
                    if(!map2.containsKey(sum)) map2.put(sum, 0);
                    map2.put(sum, map2.get(sum)+1);
                }
            }
            int ret = 0;
            for(Integer key1 : map1.keySet()){
                if(map2.containsKey(-key1)) ret += map1.get(key1) * map2.get(-key1);
            }
            return ret;
        }
    }
    

  • 0
    Y

    same as mine,but actually we can just use 1 hashmap,which will be faster.


Log in to reply
 

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