哈希
解题思路
将 A、B、C、D 四个数组两两一组进行分组，对 A、B 进行二重循环，并将
A[i] + B[j]的结果作为 key 放入 map 中，将求和的个数放入对应的 value 中，形成对应的 k-v 映射，即 和为 k 的结果出现了 v 次；由于题干要找到
A[i] + B[j] + C[k] + D[l] = 0的结果数量，可知A[i] + B[j] = -(C[k] + D[l])，则可以对 C、D 二重循环在 map 中寻找等于-(C[k] + D[l])的 key 值，将-(C[k] + D[l])对应的 value 累加起来；
复杂度
-
时间复杂度：
O(n^2)，使用了两次二重循环； -
空间复杂度：
O(n^2)，即为哈希映射需要使用的空间；在最坏的情况下，A[i]+B[j]的值均不相同，因此值的个数为 n^2；
代码实现
var fourSumCount = function (nums1, nums2, nums3, nums4) {
let res = 0;
const hash = new Map();
for (let i = 0; i < nums1.length; i++) {
for (let j = 0; j < nums2.length; j++) {
const sum = nums1[i] + nums2[j];
let num = hash.get(sum) || 0;
hash.set(sum, ++num);
}
}
for (let i = 0; i < nums3.length; i++) {
for (let j = 0; j < nums4.length; j++) {
const sum = - (nums3[i] + nums4[j]);
if (hash.has(sum)) {
res += hash.get(sum);
}
}
}
return res;
};
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 202. 快乐数
上一篇
评论
