給定四個包含整數的陣列串列 A、B、C、D，計算有多少個元組 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0，為了使問題簡單化，所有的 A, B, C, D 具有相同的長度 N，且 0 ≤ N ≤ 500 ，所有整數的范圍在 -228 到 228 - 1 之間，最終結果不會超過 231 - 1
解題思路
使用 HashMap，將 A、B 分為一組，C、D 分為一組，首先求出 A 和 B 任意兩數之和 sumAB，以 sumAB 為 key，sumAB 出現的次數為 value，存入 HashMap 中，然后計算 C 和 D 中任意兩數之和的相反數 sumCD，在 hashmap 中查找是否存在 key 為 sumCD，有則計數加一，演算法時間復雜度為 O(n2)
class Solution {
public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
Map<Integer, Integer> map = new HashMap<>();
int res = 0;
for(int i = 0; i < A.length; i++) {
for(int j = 0; j < B.length; j++) {
int sumAB = A[i] + B[j];
if(map.containsKey(sumAB)) {
map.put(sumAB, map.get(sumAB) + 1);
} else {
map.put(sumAB, 1);
}
}
}
for(int i = 0; i < C.length; i++) {
for(int j = 0; j < D.length; j++) {
int sumCD = -(C[i] + D[j]);
if(map.containsKey(sumCD)) {
res += map.get(sumCD);
}
}
}
return res;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/228731.html
標籤：其他
上一篇：0395. Longest Substring with At Least K Repeating Characters (M)