目录

题目

思路

代码 

---

题目

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

思路

先遍历前两个数组，得到两数相加a，然后遍历后两个，得到b，看0-a是否在等于b，即在集合中查找是否有某个元素，所以想到用哈希表

元组：可用于数据存储，包含多个数据；但是和列表不同的是：列表只能存储相同的数据类型，而元组不一样，它可以存储不同的数据类型，比如同时存储int、string、list等，并且可以根据需求无限扩展。

哈希表的三种结构：有数组，set，map

• 不可用数组：因为题目中所给是元组，元组可以存放任意数据类型，他的长度不固定，如果用数组的话长度无法确定，所以无法用数组
• 不可用set，我们在存储时，不仅要你存储出现了那些数字，还要存储他们出现的次数，而set只能存储出现过什么，不可以存储出现次数
• 综上，使用map

map中key存储出现的次数和，value存储出现的次数 

为什么要先遍历前两个数组 ，再遍历后两个数组？

遍历前两个数组时，时间复杂度为n^2，遍历后两个数组时候时间复杂度也为n^2，算法总体时间复杂度为n^2

如果我们先遍历第一个数组，然后再遍历后三个数组， 遍历第一个数组时间的复杂度为n，后三个为n^3,算法总体时间复杂度为n^3,

所以两个两个更优。

易错点

如果0-a等于b，那么count不应该+1，而是应该加value，举例即可明白。

代码 

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int res=0;//统计最后符合条件的个数Map<Integer,Integer> map=new HashMap<Integer,Integer>();//定义一个mapfor(int i:nums1){//遍历前两个元素for(int j:nums2){int a=i+j;//得到两数之和amap.put(a,map.getOrDefault(a,0)+1);//键：a,如果没有存放过这个键，那么这个键的初始值为1，如果有，那么把他的键取出，j+，在放入map中
//对 map 中以 sum 为键的值进行计数操作。它会检查 map 中是否已经存在键为 sum 的项，如果存在，则将其对应的值加 1；如果不存在，则将 sum 作为键添加到 map 中，并将其值初始化为 1。}}for(int i:nums3){//遍历后两个数组for(int j:nums4){res+=map.getOrDefault(0-i-j,0);
//将 map 中键为 0 - i - j 的值累加到变量 res 中。如果 map 中不存在键为 0 - i - j 的键值对，那么将使用默认值 0 进行累加操作。}}
return res;}
}