前言

在本科毕设结束后，我开始刷卡哥的“代码随想录”，每天一节。自己的总结笔记均会放在“算法刷题-代码随想录”该专栏下。
代码随想录此题链接

题目

给你四个整数数组 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

提示：

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

1. 哈希表

思路（定义变量）

1. 此题定义一个unordered_map，用来存储前两个vector中元素遍历组合的和。
2. count用来记录值

2. 本题思路分析：

1. 四个vector的数组，要将其抽象看成两个数组。将2个vector遍历相加，存入一个unordered_map类型的map对象中（map的键是前两个vector元素相加的和，值是计算这个相加的和出现的次数）。
2. 剩下的两个vector进行遍历累加，每次产生的和sum，判断在map对象中是否有其相反数，如果有就让count累加上对应的次数（map对应的值）。

3. 算法实现

• 代码：

#include 
#include 
#include 
#include 
using namespace std;
//取各个位上的平方和 
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
	unordered_map<int,int> matches;
	int count = 0; 
	//对nums1、nums2 两个数组计算全部的和 
	for(int i = 0;i < nums1.size();i++){
		for(int j = 0;j < nums2.size();j++){
			matches[nums1[i] + nums2[j]]++;
		}
	}
	//对nums3、nums4 两个数组计算全部的和 
	for(int i = 0;i < nums3.size();i++){
		for(int j = 0;j < nums4.size();j++){
			int another = 0 - (nums3[i] + nums4[j]);
			if(matches.find(another) != matches.end()){
				//如果找到匹配为0的情况 
				count += matches[another];
			}
		}
	}
	return 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

4. 算法复杂度

1. 时间复杂度：O(n^2)
2. 空间复杂度：O(n)

5. 算法坑点

1. 没想到可以将前两个vector的值遍历累加存放到一个unordered_map中，有点类似代码随想录-023-1.两数之和中，将第一个vector存入unordered_map中，（map的键是vector里元素对应的值，map的值是元素在vector中的下标）；而这道题是将两个vector中遍历值的和存入map的键，出现这个和的次数存为对应map的值。