454. 4Sum II

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.

題目大致是說給四個陣列(長度一樣),然後每一個陣列挑一個元素出來,問有幾組和為0

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)

這邊有個還不錯的解,算是我之前想利用再來解 3Sum 的地方

不過之前那題比較麻煩是因為那題需要print出當前的那一組,這題不用的話就可以放心地用hashmap

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.