➕︎ 454.四数相加
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
思路
基本思想
为了求出四个数的和，最简单的方法就是使用四层嵌套for循环，暴力求解，但是这样会超时，所以需要将问题分解
四个数可以分成两个数一组，第一组求和，第二组求和，形成新的求和数组之后，四数之和就变成了两数之和，为了进一步减小运行时间，第一组求和的数组可以用哈希表存储，这样在第二组数求和的过程中就可以判断求和之后第一组中是否有符合要求的数
由于两组数求和可能会出现同一个答案，所以需要将求和之后的数出现的次数进行统计，这样第二组数求和统计时，就可以直接得出当前会出现几个0
核心就是将四组数两两分组
执行流程
- 四组数两两分组，第一组数求和形成哈希表
- 第二组数求和，并判断第一组数中是否有相加为0的元素
- 统计所有出现0的组合
- 返回结果
代码
根据以上分析，得出以下代码：
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
| class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
//将四个数分成两个数一组，第一组负责构建哈希表，第二组负责在哈希表中查找
//哈希表的键值代表<值，出现次数>
//创建哈希表
unordered_map<int,int> umap;
for(int i=0;i<nums1.size();++i){
for(int j=0;j<nums2.size();++j){
umap[nums1[i]+nums2[j]]+=1;
}
}
//在哈希表中查找是否有符合条件的元素
int res=0;
for(int i=0;i<nums3.size();++i){
for(int j=0;j<nums4.size();++j){
//添一个负号，查看哈希表中是否有元素可以相加之后等于0
if(umap[-(nums3[i]+nums4[j])]>0){
//一旦有相加和为0的元素，出现几次说明就可以相加出现几个0
res+=umap[-(nums3[i]+nums4[j])];
}
}
}
return res;
}
};
|
总结
主要是将问题拆分，四数之和变成两组数之和，由于同一个数的可能出现多次，例如4+1与2+3都是5的这种情况，需要统计一个数的出现次数，一旦这个数存在另外一个数相加为0，那么形成这个数的所有情况都需要统计