使用C++解决这问题:454. 四数相加 II 中等 826 相关企业 给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足: 0 <= i, j, k, l < n nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
时间: 2024-02-27 19:58:19 浏览: 74
这是一个经典的问题,可以使用哈希表来解决。
首先,我们可以将 nums1 和 nums2 中所有数字的和存入一个哈希表中,键为两个数字的和,值为这个和出现的次数。
接着,我们遍历 nums3 和 nums4 中所有数字的和,查找哈希表中是否有相反数(即相加为 0)。如果有,将其对应的出现次数累加到答案中。
具体实现过程如下:
```c++
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> hash;
int n = nums1.size(), res = 0;
// 存储 nums1 和 nums2 中所有数字的和
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
hash[nums1[i] + nums2[j]]++;
}
}
// 遍历 nums3 和 nums4 中所有数字的和,查找哈希表中是否有相反数
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
int target = -(nums3[i] + nums4[j]);
if (hash.count(target)) {
res += hash[target];
}
}
}
return res;
}
```
时间复杂度为 $O(n^2)$,空间复杂度为 $O(n^2)$。
阅读全文