【刷题日记】哈希表-四数相加II-L454-Medium
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
思路
- 与
L1. 两数之和 思路类似，寻找 target - x。为了降低时间复杂度，因此将 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0 分组为 nums1[i] + nums2[j] = 0 - nums3[k] - nums4[l]，先对 nums1 + nums2 遍历，并存储已出现的元素和以及其个数；然后遍历 nums3 + nums4，并查找当前元素和的相反数以及其出现个数。
学习点
- 借鉴
L1. 两数之和 的思路，进行 分组 + 哈希表。
代码
修改前：（超出时间限制）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
multiset<int> ms;
int res = 0;
int nums_size = nums1.size();
for (int i = 0; i < nums_size; ++i)
{
for (int j = 0; j < nums_size; ++j)
{
ms.insert(nums1[i] + nums2[j]);
}
}
for (int i = 0; i < nums_size; ++i)
{
for (int j = 0; j < nums_size; ++j)
{
int opp_count = ms.count(0 - nums3[i] - nums4[j]);
if (opp_count)
res += opp_count;
}
}
return res;
}
};
|
修改后代码，没有超过时间限制，可能 multiset 的 insert 和 count 函数时间复杂度较高。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> um;
int res = 0;
int nums_size = nums1.size();
for (int i = 0; i < nums_size; ++i)
{
for (int j = 0; j < nums_size; ++j)
{
++um[nums1[i] + nums2[j]];
}
}
for (int i = 0; i < nums_size; ++i)
{
for (int j = 0; j < nums_size; ++j)
{
int opp_count = um[0 - nums3[i] - nums4[j]];
if (opp_count)
res += opp_count;
}
}
return res;
}
};
|
