代码随想录Day6哈希表：454四数相加II_383赎金信_15三数之和_18四数之和

代码随想录Day6哈希表：454四数相加II_383赎金信_15三数之和_18四数之和

454 四数相加

题目：给你四个整数数组 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
解释：两个元组如下：
(0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
(1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
链接：https://leetcode.cn/problems/4sum-ii/

思路上像Day5的1两数之和，只不过那是两个数字，这里变成两个数组。使用map。

classSolution{publicintfourSumCount(int[] nums1,int[] nums2,int[] nums3,int[] nums4){Map<Integer,Integer> map=newHashMap<Integer,Integer>();int result=0;for(int i:nums1){for(int j:nums2){int sum=i+j; map.put(sum, map.getOrDefault(sum,0)+1);}}for(int i:nums3){for(int j:nums4){ result=result+map.getOrDefault(0-i-j,0);}}return result;}}

注意map.getOrDefault的用法：map.getOrDefault(sum, 0); 如果sum这个key存在则返回对应的value，不存在就返回0。
map.put(sum, map.getOrDefault(sum, 0) + 1); 是统计频率的常见写法。

383赎金信

题目：给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：输入：ransomNote = “a”, magazine = “b”，输出：false
示例 2：输入：ransomNote = “aa”, magazine = “ab”，输出：false
示例 3：输入：ransomNote = “aa”, magazine = “aab”，输出：true
链接：https://leetcode.cn/problems/ransom-note/

思路和day5的242有效的字母异位词思路一样。定义一个26长度的数组，下标是字母的相对顺序，存储的值是magazine中字母出现的频率。

classSolution{publicbooleancanConstruct(String ransomNote,String magazine){if(ransomNote.length()> magazine.length()){returnfalse;}int[] array=newint[26];for(char c:magazine.toCharArray()){//magazine.toCharArray()将字符串转换为字符数组 array[c-'a']+=1;}for(char d:ransomNote.toCharArray()){ array[d-'a']-=1;}for(int i:array){if(i<0){returnfalse;}}returntrue;}}

15 三数之和

题目：给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。注意：答案中不可以包含重复的三元组。
示例 1：输入：nums = [-1,0,1,2,-1,-4]，输出：[[-1,-1,2],[-1,0,1]]
解释：nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
链接：https://leetcode.cn/problems/3sum/

这个题的关键难点在于不能输出包含重复的三元组。因此需要去重，先把数组排好序，这样之后去重其实就是跳过那个数字，比如数组中的一部分为[2,2,3]，遍历了第一个2之后直接跳过第二个2就行。

双指针法：

classSolution{publicList<List<Integer>>threeSum(int[] nums){List<List<Integer>> result=newArrayList<>();Arrays.sort(nums);for(int i=0; i<nums.length; i++){if(nums[i]>0){return result;}if(i>0&& nums[i]==nums[i-1]){//去重第一个元素acontinue;}int left=i+1;int right=nums.length-1;while(left<right){int sum = nums[i]+ nums[left]+ nums[right];if(sum>0){ right--;}elseif(sum<0){ left++;}else{ result.add(Arrays.asList(nums[i], nums[left], nums[right]));// 去重bc的逻辑应该放在找到一个三元组之后，对b 和 c去重while(left<right && nums[right]==nums[right-1]){ right--;}while(left<right && nums[left]==nums[left+1]){ left++;} right--; left++;}}}return result;}}

这段代码的判断里有几个很容易错的点：
a的去重：a 如果重复了怎么办，a是nums里遍历的元素，那么应该直接跳过去。但这里有一个问题，是判断 nums[i] 与 nums[i + 1]是否相同，还是判断 nums[i] 与 nums[i-1] 是否相同。

bc去重的逻辑在找到一个三元组之后，没必要多加。

最后bc去重完了之后还有一个right–; left++; 这个操作，在写的时候忘记了。

18四数之和

题目：给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）。
示例 1：输入：nums = [1,0,-1,0,-2,2], target = 0，输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
链接：https://leetcode.cn/problems/4sum/

和三数之和是一个思路，双指针法，但是更复杂。
复杂在于两点：1 需要再套一层for循环；2 三数之和的target是固定的0，这里没有固定，在剪枝的时候更复杂。

不要判断nums[k] > target 就返回了，三数之和可以通过 nums[i] > 0 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。比如：数组是[-4, -3, -2, -1]，target是-10，不能因为-4 > -10而跳过。但是我们依旧可以去做剪枝，逻辑变成nums[k] > target && (nums[k] >=0 || target >= 0)就可以了。

classSolution{publicList<List<Integer>>fourSum(int[] nums,int target){List<List<Integer>> result =newArrayList<>();Arrays.sort(nums);for(int i=0; i<nums.length; i++){if(nums[i]>target && nums[i]>=0){//剪枝break;}if(i>0&& nums[i]==nums[i-1]){//去重continue;}for(int j=i+1; j<nums.length; j++){if(nums[i]+nums[j]>target && nums[i]+nums[j]>=0){//第二个元素的剪枝break;}if(j>i+1&& nums[j]==nums[j-1]){//第二个元素的去重continue;}int left=j+1;int right=nums.length-1;while(left<right){int sum=nums[i]+nums[j]+nums[left]+nums[right];if(sum>target){ right--;}elseif(sum<target){ left++;}else{ result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));// 对nums[left]和nums[right]去重while(left<right && nums[right]==nums[right-1]){right--;}while(left<right && nums[left]==nums[left+1]){left++;} right--; left++;}}}}return result;}}

小结

哈希表都是用来快速判断一个元素是否出现集合里。

三种数据结构：数组，set，map
用哈希表的时候要判断哪种数据结构更合适：
1 有些用map确实可以，但使用map的空间消耗要比数组大一些，因为map要维护红黑树或者符号表，而且还要做哈希函数的运算。
2 数组和set：数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
3 map作为哈希表：数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。map是一种<key, value>的结构，可以用key保存数值，用value在保存数值所在的下标。

具体情况如何判断，有没有想到用哈希表还需要熟练一点。