NO IMAGE

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there
are such that A[i] B[j] C[k] D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 –
1 and the result is guaranteed to be at most 231 – 1.

Example:

Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]
Output:
2
Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0]   B[0]   C[0]   D[1] = 1   (-2)   (-1)   2 = 0
2. (1, 1, 0, 0) -> A[1]   B[1]   C[0]   D[0] = 2   (-1)   (-1)   0 = 0

思路:brute force就是N^4,優化點,就會想到Two Sum用hashmap提速,演算法就是:先算A,B的元素和,key是sum,value是次數。然後算C D的和,看負的C D的和是否能在之前A B中出現過,出現了就加入res.

public class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
if(A == null || B == null || C == null || D == null 
|| A.length == 0 || B.length == 0 || C.length == 0 || D.length == 0){
return 0;
}
HashMap<Integer, Integer> hashmapAB = new HashMap<Integer, Integer>();
for(int i=0; i<A.length; i  ){
for(int j=0; j<B.length; j  ){
int sum = A[i] B[j];
Integer k = hashmapAB.get(sum);
if(k == null){
hashmapAB.put(sum, 1);
} else {
hashmapAB.put(sum, k 1);
}
}
}
int res = 0;
for(int i=0; i<C.length; i  ){
for(int j=0; j<D.length; j  ){
int target = (-1)*(C[i] D[j]);
Integer k = hashmapAB.get(target);
if(k != null){
res  = k;
}
}
}
return res;
}
}