Clean java solution O(n^2)

• ``````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)``````

• Time complexity: O(lgn * n^2)?

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

• @asurana28
map search one element is O(1）？

• @liyi193328
HashMap amortized time complexity for get & put is O(1).

• exactly the same as mine. Good solution

• 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;
}
}``````

• Hashing is so powerful!

• 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) .

• Oh,is my mistake.I have read source code of HashMap class carefully last night,and those methods' complexity is O(1) or O(n),it depends on the length of entry array and the entry link,

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

• @asurana28 Yes,you are right. it does 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 = -c-d;
result += map.getOrDefault(s, 0);
}
return result;
}
``````

• Why should they have the same length? Even the length is different, the code still works.

• map.getOrDefault(-1 * (A[i]+B[j])

why -1 here ? Can someone please explain?

• -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.

• @asurana28

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;
}
}
``````

• This post is deleted!

• ``````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;
}``````

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