mirror of
https://github.com/ShusenTang/LeetCode.git
synced 2024-09-02 14:20:01 +00:00
37 lines
1.2 KiB
Markdown
37 lines
1.2 KiB
Markdown
# [454. 4Sum II](https://leetcode.com/problems/4sum-ii/)
|
||
|
||
# 思路
|
||
|
||
从四个数组中各取一个数字，使其和为0，问有多少种取法。如果暴力四重循环的话复杂度为O(n^4)，是不可接受的。 我们可以采用hashmap将前两个数组的元素的和存放起来，这样就可以将复杂度降至O(n^2)。
|
||
|
||
注意如果某个元素不在hashmap中，如果我们访问了它，那它会被插入到hashmap中，例
|
||
``` C++
|
||
unordered_map<int, int>mp;
|
||
int a = mp[2];
|
||
if(mp.count(2)) cout << "2 is in mp!" ; // 会输出
|
||
```
|
||
|
||
|
||
# C++
|
||
``` C++
|
||
class Solution {
|
||
public:
|
||
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
|
||
int res = 0;
|
||
unordered_map<int, int>abSum;
|
||
for(int a: A)
|
||
for(int b: B)
|
||
abSum[a+b]++;
|
||
|
||
for(int c: C)
|
||
for(int d: D){
|
||
// 以下两行比直接 res += abSum[-c-d] 要快,
|
||
// 因为如果 -c-d 不在abSum中, 访问abSum[-c-d]会将-c-d插入abSum中
|
||
auto it = abSum.find(-c-d);
|
||
if(it != abSum.end()) res += it -> second;
|
||
}
|
||
|
||
return res;
|
||
}
|
||
};
|
||
``` |