力扣454四数相加

文章目录

1、题目要求2、思路分析3、执行代码 - Java4、问题反思

4.1、为什么Map 是下面的这个定义4.2、为什么是：map.get(temp)4.3、为什么第二个循环这样子写？4.4、为什么是 res += map.get(0 - temp); 5、小结
题目链接

https://leetcode-cn.com/problems/4sum-ii/

源代码 github 地址

https://github.com/YIMEng-0/DataStructure

1、题目要求

https://leetcode-cn.com/problems/4sum-ii/

2、思路分析

使用分而治之的思想，四个数组的和，调整为两个数组相加，另外两个数组相加的形式;在第一个数组中统计相加的结果以及相加的结果出现的次数;另一个数组中统计相加的结果以及结果出现的次数，不同的是需要在HashMap 中寻找是否存在满足 map.get(0 - temp) 因为 a + b = 0; b = 0 - a; 3、执行代码 - Java

class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { // 使用分而治之的思想，四个数组的和，调整为两个数组相加，另外两个数组相加的形式 // 在第一个数组中统计相加的结果以及相加的结果出现的次数 // 另一个数组中统计相加的结果以及结果出现的次数，不同的是需要在HashMap 中寻找是否存在满足 map.get(0 - temp) 因为 a + b = 0; b = 0 - a; Map map = new HashMap<>(); // 统计满足题目要求的数组的次数 int res = 0; // 将前两个数组中的所有元素求和，存储结果以及结果出现的次数 for(int i : nums1) { for(int j : nums2) { int temp = i + j; if(map.containsKey(temp)) { map.put(temp,map.get(temp) + 1); } else { map.put(temp,1); } } } // 将后面的两个数组求和处理，寻找存储在哈希表中 key 的相反数以及相反数出现的次数； for(int i : nums3) { for(int j : nums4) { int temp = i + j; if(map.containsKey(0 - temp)) { res += map.get(0 - temp); } } } return res; }}

4、问题反思 4.1、为什么Map 是下面的这个定义

Map map = new HashMap<>();
存储到 HashMap 结构中的元素，key 是两个数组中元素分别求和的结果，value 是求和结果出现的次数；
由于都是整型，所有就是 Integer,Integer 的形式；

4.2、为什么是：map.get(temp)

通过 key 获取到 value 的方法，在这里的体现就是通过相加的结果获取到相加结果存在的次数；

4.3、为什么第二个循环这样子写？

if(map.containsKey(0 - temp)) { res += map.get(0 - temp);}

a + b = 0;
a = 0 - b;
最终的结果由前两个数组中求和结果出现的次数决定， containsKey() 是一种查询的结果；

4.4、为什么是 res += map.get(0 - temp);

前面两个数组经过每两项的组合之后，出现了组合之后的和以及结果；假如前面两个数组求和之后出现了5次 5 ，在后面两个数组中出现了一次 -5 那么就可以组合成为 5 次为 0 的结果，因为前面的每一个 5 都可以和后面的 -5 组合成为 0 ，满足题目要求；

5、小结

通过使用哈希表，将两两数组的和保存在 HashMap 中，方便快速查询操作，提高了效率，本题目还涉及到分而治之的思想，如果直接使用四层循环可以做但是时间复杂度太高，使用了两两组组合的形式，可以有效的降低时间复杂度，提高算法的性能；