454.四数相加 II
一、题目
给你四个整数数组 nums1
、nums2
、nums3
和 nums4
,数组长度都是 n
,请你计算有多少个元组 (i, j, k, l)
能满足:
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1:
输入:nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出:2
解释:
两个元组如下:
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2:
输入:nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出:1
提示:文章来源:https://www.toymoban.com/news/detail-523467.html
n == nums1.length
n == nums2.length
n == nums3.length
n == nums4.length
1 <= n <= 200
-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
二、解法
方法一:哈希法
算法思路
- 初始化一个哈希表
sumAB
,用于记录数组nums1
和nums2
中元素的和及其出现的次数。 - 遍历数组
nums1
和nums2
的所有元素组合,并将元素和及其出现次数存储在sumAB
中。 - 初始化一个变量
count
,用于记录满足条件的四元组的个数,初始值为 0。 - 遍历数组 nums3 和 nums4的所有元素组合:
- 计算当前两个元素的和
target
。 - 在
sumAB
中查找是否存在和为target
的相反数。 - 如果存在相反数,将对应的出现次数累加到
count
中。
- 计算当前两个元素的和
- 返回
count
作为最终的结果。
详细实现
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int count = 0;
unordered_map<int, int> sumAB; // 记录 nums1 和 nums2 的元素和及其出现次数
// 遍历 nums1 和 nums2,记录元素和及其出现次数
for (int num1 : nums1) {
for (int num2 : nums2) {
sumAB[num1 + num2]++;
}
}
// 遍历 nums3 和 nums4,查找目标和的相反数,并累加对应的次数到结果中
for (int num3 : nums3) {
for (int num4 : nums4) {
int target = -(num3 + num4);
if (sumAB.find(target) != sumAB.end()) {
count += sumAB[target];
}
}
}
return count;
}
};
算法分析
- 时间复杂度:算法的时间复杂度为 O(n^2),其中 n 是数组的长度。遍历数组
nums1
和nums2
的时间复杂度为 O(n^2),遍历数组nums3
和nums4
的时间复杂度也为 O(n^2),因此总的时间复杂度为 O(n^2)。 - 空间复杂度:算法使用了一个哈希表
sumAB
来存储元素和及其出现次数,哈希表的大小最多为数组nums1
和nums2
的组合数,即 O(n^2)。因此,算法的空间复杂度为 O(n^2)。
方法二:两个哈希表(方法一的复杂版,不推荐)
这是一个不好的办法,超出了时间限制,各位看官看看即可……文章来源地址https://www.toymoban.com/news/detail-523467.html
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int n = nums1.size();
int count = 0;
//创建两个哈希表,key值为两个数组元素的和,value值为组成这个和的两个下标
multimap<int,multimap<int,int>> numA;
multimap<int,multimap<int,int>> numB;
for(int i = 0; i < n; i++){
for(int j = 0; j < n;j++){
numA.insert(make_pair(nums1[i] + nums2[j], multimap<int, int>{{i, j}}));
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n;j++){
numB.insert(make_pair(nums3[i] + nums4[j], multimap<int, int>{{i, j}}));
}
}
//遍历numA寻找numB中对应元素
for(auto iterA = numA.begin();iterA != numA.end();iterA++){
for(auto iterB = numB.begin();iterB != numB.end();iterB++){
if(iterA->first + iterB->first == 0){
count++;
}
}
}
return count;
}
};
到了这里,关于LeetCode 454.四数相加 II的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!