难度中等741
给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：
0 <= i, j, k, l < nnums1[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.lengthn == nums2.lengthn == nums3.lengthn == nums4.length1 <= n <= 200-228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228
解题思路：哈希表
学透哈希表，map使用有技巧！LeetCode：454.四数相加II
这道题如果直接遍历四个数组的话，那么这个时间复杂度高到非常可怕，是O(n^4)，所以我们肯定不能直接去暴力遍历！
这道题的要求的意思就类似深度遍历一般，要求每个四数等于0的解的个数，那么我们其实可以拆分为两个数组和两个数组进行相加，假设这里是 A、B、C、D 分别四个数组，我们只需要两两进行比较，也就是我们先遍历前两个数组中，将两个数组的值分别相加起来，就得到了前两个数组各位相加的和 a+b 以及出现的次数！
接着我们遍历后两个数组，将后两个数组各位的和 c+d 与前两个数组各位的和 a+b 进行比较，题目要求说 a+b+c+d = 0，那么我们只要让 a + b = 0 - c - d 也就是 a+b = 0 - (c + d)，意思就是每次判断 0 - (c + d) 是否等于 a+b 即可！为了快速的得到我们之前的 a+b，我们采用哈希表，由于没有顺序要求，我们可以使用C++中的 unordered_map 进行收集，其中 key 为前两个数组各位的和 a+b，value为各位和出现的次数！
🐎 注意还有一个细节就是每次这个四数之和的解 sum 是 sum++ 吗？其实不是的，sum 要加上 hash[0 - c - d] 出现的个数，比如说在 A 和 B 数组中出现了三次相加为 5 的和，而 C 和 D 数组中出现了一次相加为 -5 的和，那么结果就是 sum += 3，而不是 sum += 1，这个是要注意的！
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int n = nums1.size();
unordered_map<int, int> hash; // key:a+b的数值，value:a+b数值出现的次数
// 先将nums1和nums2的和以及出现次数放到hash中
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
hash[nums1[i] + nums2[j]]++;
// 接着用0减去nums3和nums4的和，若等于某个nums1和nums2的和则sum++
int sum = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
if(hash.count(0 - nums3[i] - nums4[j]))
sum += hash[0 - nums3[i] - nums4[j]];
return sum;
}
}; 通过这种遍历方式，最后优化的时间复杂度为 O(n^2)，我们是能够接收的！那么会有人问，为什么不是先遍历第一个数组，再遍历后三个数组，因为这样子的话时间复杂度就高了，变成了 O(n^3)，优化还没到最大程度！
