public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
Map<Integer, Integer> map = new HashMap<>();
for(int i=0; i<C.length; i++) {
for(int j=0; j<D.length; j++) {
int sum = C[i] + D[j];
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
int res=0;
for(int i=0; i<A.length; i++) {
for(int j=0; j<B.length; j++) {
res += map.getOrDefault(1 * (A[i]+B[j]), 0);
}
}
return res;
}
Time complexity: O(n^2)
Space complexity: O(n^2)
Clean java solution O(n^2)


@liyi193328
Time complexity for both the outer forloops is O(n^2) since statements inside inner loops are O(1). What makes you think it's O(logn * n^2)?



Similar Idea 
public class Solution { public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { int n = A.length; if (n == 0) return 0; HashMap<Integer, Integer> map = new HashMap<>(); int res = 0, sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { sum = A[i] + B[j]; map.put(sum, map.getOrDefault(sum, 0) + 1); } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { sum = C[i] + D[j]; res += map.getOrDefault(sum, 0); } } return res; } }

same idea for c++ version
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) { unordered_map<int,int> m; int res = 0; for(int i=0; i < A.size(); i++) for(int j=0; j < B.size(); j++) m[A[i]+B[j]]++; for(int i=0; i < C.size(); i++) for(int j=0; j < D.size(); j++) res += m[1*(C[i]+D[j])]; return res; }

@asurana28 I don't agree with you.The time complexity of method getOrDefault is O(logN) just like binary search when it works.So,the total complexity is O(logN * N^2) .

@FuZhihong Amortized time complexity of method getOrDefault in HashMap is O(1).


thanks for sharing, the following is my more concise code:
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int a : A) for(int b : B){ int s = a+b; map.put( s, map.getOrDefault(s, 0)+1 ); } int result=0; for(int c : C) for(int d : D){ int s = cd; result += map.getOrDefault(s, 0); } return result; }

@asurana28 said in Clean java solution O(n^2):
map.getOrDefault(1 * (A[i]+B[j])
why 1 here ? Can someone please explain?

@jpankhan said in Clean java solution O(n^2):
1 here ? Can someone please
The HashMap contains sum of all the pairs from C and D. Now we have a pair(say X) from which is sum from A and B (A[i]+B[j]) and we need to check if there is something in the HashMap which when added to X will give us zero. And we can have sum = 0 of two pairs(X and one from map) only if there is a corresponding negative value of X i.e X in the Hashmap, so we just check that if there is X in the map or not. If yes, we have a result and will add in our result variable else just add 0.

Somehow I think this looks even cleaner:
public class Solution { public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { Map<Integer, Integer> freqs = new HashMap<>(); for (int c : C) { for (int d : D) { freqs.put(c + d, freqs.getOrDefault(c + d, 0) + 1); } } int count = 0; for (int a : A) { for (int b : B) { count += freqs.getOrDefault(a  b, 0); } } return count; } }

public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { int n = A.length; Map<Integer, Integer> map = new HashMap(); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ int k = A[i] + B[j]; int v = map.getOrDefault(k, 0) + 1; map.put(k, v); } } int res = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ int s = C[i] + D[j]; if(map.containsKey(s)){ res += map.get(s); } } } return res; }