卷进大厂系列之LeetCode刷题笔记：四数相加 II（中等）

学算法，刷力扣，加油卷，进大厂！

题目描述

力扣题目链接

给你四个整数数组 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 = 02. (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

涉及知识点

这道题目虽然看着是和数组相关的题目，好像我们直接用暴力求解就能有结果，毕竟就是一个简单的四个数组中元素分别求和。但是，作为一个中等题目，这样是不是有点说不过去。确实，这样做的话，会超时。所以我们需要用另一种数据结构来解决这个题目，即哈希表。

• 数组是一个简单的哈希表，其中哈希表中的关键码就是数组的索引下标
• 哈希表可以根据关键码直接访问数据
• HashMap中的containsKey可以判断哈希表中是否有这个值

那么根据题目，我们可以提炼的关键点：

• 计算满足条件的元组个数
• 数组长度n满足：1 <= n <= 200

题目解答

Java题解一

直接暴力求解，通过使用四个for循环对四个数组内数字分别求和，将满足条件的结果进行计数。（超时了，别用了，我就是放出来让大家看看）

class Solution {    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { int result = 0; //输出结果 //暴力解法:直接四个for循环，将每个数组里的元素都求和试一下 for(int i = 0; i < nums1.length; i++){     for(int j = 0; j < nums2.length; j++){  for(int k = 0; k < nums3.length; k++){      for(int v = 0; v < nums4.length; v++){   if(nums1[i]+nums2[j]+nums3[k]+nums4[v] == 0){result++; //满足条件result就加一   }      }  }     } } return result;    }}

Java题解二

使用哈希表

• 定义HashMap用来存放前两个数组的和，其中key是前两个数组的和，value是求和后该值的个数
• 首先计算前两个数组中各元素的和，并统计各个结果的个数
• 然后计算后面两个数组的和，用containsKey判断是否与HashMap中某个值的和为0
• 如果有，则获取其value值，并累加到结果中

class Solution {    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { //使用HashMap，利用其映射关系，key存前两个的和，value该值的个数 HashMap<Integer, Integer> hashmap = new HashMap<>(); int temp; //用来临时存前两个元组的和 int reuslt = 0; //定义输出结果 //计算前两个元组的和 for(int i : nums1){     for(int j : nums2){  temp = i + j; //前两个元组的元素分别求和，放在temp  if(hashmap.containsKey(temp)){ //判断下哈希表中有没有这个值      hashmap.put(temp,hashmap.get(temp)+1);//如果有，找到对应value值加1  }else{      hashmap.put(temp,1); //没有的话，放入哈希表，value赋值为1  }     } } //计算后两个元组的和， for(int i : nums3){     for(int j : nums4){  temp = i+ j; //后两个元组的元素分别求和，放在temp  if(hashmap.containsKey(0-temp)){ //在hashmap中找是否存在相加和为0的情况      reuslt += hashmap.get(0-temp); //进行统计结果  }     } } return reuslt; //返回结果    } }

多事通