Leecode刷题 Day7----------哈希表

1. 四数相加II（454）

• 题目链接：https://leetcode.cn/problems/4sum-ii/
• 文章讲解/视频讲解：https://programmercarl.com/0454.%E5%9B%9B%E6%95%B0%E7%9B%B8%E5%8A%A0II.html

重点：

• 不用去重，两组0000，0000分别来自四个数组，但是每个0来自一个数组的不同位置。这样算两组，无需去重。
• 重点在于Map的key是分别第一个数组和分别第二个数组的和，value是这个和出现的次数！ 类似于两数之和！
• count+=map.get(0-temp); 意味着这么多组不去重！

class Solution {public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {Map map=new HashMap<>();int count=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);}}for(int i:nums3){for(int j:nums4){int temp=i+j;if(map.containsKey(0-temp)) count+=map.get(0-temp);}}return count;}
}

2. 赎金信 （383）

• 题目链接：https://leetcode.cn/problems/ransom-note/
• 文章讲解：https://programmercarl.com/0383.%E8%B5%8E%E9%87%91%E4%BF%A1.html

重点：与字母异位很类似！！！！只要有<0，就是false

class Solution {public boolean canConstruct(String ransomNote, String magazine) {int[] ints=new int[26];for(int i=0;iints[magazine.charAt(i)-'a']++;}for(int i=0;iints[ransomNote.charAt(i)-'a']--;}for(int i=0;iif(ints[i]<0) return false;}return true;}
}

3. 三数之和 （15）

• 题目链接：https://leetcode.cn/problems/3sum/
• 文章讲解/视频讲解：https://programmercarl.com/0015.%E4%B8%89%E6%95%B0%E4%B9%8B%E5%92%8C.html

重点：

1. 题意表明要去重！！！000可以的，如果有两组000是不行的（因为原数组里可能有重复的0，四个0等）
2. 三个数字的去重方式不同：
   2.1 第一个数字是在开始的时候就去重，如果这个和左边已经加过的数字相同时跳过-------if(i>0&&nums[i]==nums[i-1]) continue;
   2.2 第二个数字left是如果下一个和这个相同时就直接给指针+±-------while(right > left&&nums[left]==nums[left+1]) left++;
   2.3 第三个数字right是如果下一个和这个相同时就直接给指针–,---------------- while(right > left&&nums[right]==nums[right-1]) right–;
3. left = i+1
4. 判断sum 与0的关系从而控制 left 和 right 指针的移动方向
5. 注意数组不要越界，只要看到数组索引+1或-1就要敏感-----判断：i的大小&&条件
6. 库函数：list.add(Arrays.asList(nums[i], nums[left], nums[right]));

class Solution {public List> threeSum(int[] nums) {List> list=new ArrayList<>();Arrays.sort(nums);for(int i=0;iif(nums[i]>0) return list;if(i>0&&nums[i]==nums[i-1]) continue;int left=i+1;int right=nums.length-1;while(leftint sum=nums[i]+nums[left]+nums[right];if(sum>0) right--;else if(sum<0) left++;else{list.add(Arrays.asList(nums[i], nums[left], nums[right]));while(left+11 & &nums[right]==nums[right-1]) right--;left++;right--;}    }}return list;}
}

4. 四数之和 （18）

• 题目链接：https://leetcode.cn/problems/4sum/
• 文章讲解/视频讲解：https://programmercarl.com/0018.%E5%9B%9B%E6%95%B0%E4%B9%8B%E5%92%8C.html

与上题的不同点：

1. 加一层for循环，j=i+1
2. j 的判断条件：是否>i+1 && 条件
3. 不知道target与0的关系，如果该数>target并且该数为正数，这是不存在的
   if(nums[i]>0 && nums[i]>target) return list;

class Solution {public List> fourSum(int[] nums, int target) {List> list=new ArrayList<>();Arrays.sort(nums);for(int i=0;i//如果该数>target并且该数为正数，这是不存在的if(nums[i]>0 && nums[i]>target) return list;if(i>0&&nums[i]==nums[i-1]) continue;for(int j=i+1;jif(j>i+1 && nums[j]==nums[j-1]) continue;int left=j+1;int right=nums.length-1;while(leftint sum=nums[i]+nums[j]+nums[left]+nums[right];if(sum>target) right--;else if(sumlist.add(Arrays.asList(nums[i], nums[j],nums[left], nums[right]));while(left+11&&nums[right]==nums[right-1]) right--;left++;right--;}    }}}return list;}
}

5. 总结

454. 四数相加 与 18. 四数之和，15. 三数之和 的区别：

454 为四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑重复问题
18. 四数之和 ，15.三数之和 是一个数组（集合）里找到和为0的组合，难很多！