代码随想录算法训练营Day7|哈希表
454.四数相加II给你四个整数数组nums1nums2nums3和nums4，数组长度都是n，请你计算有多少个元组2两个元组如下：1就是把四个数组变成两个数组，然后就把问题转化成了两数之和的问题，要注意的是Key依然存的是元素的值，但是Value不再是存索引，而是出现Key对应元素的次数，看完老师的码我发现我铸币了，我都用getOrDefault()了，根本就不需要先一步进行containsKe
454.四数相加II
给你四个整数数组
nums1、nums2、nums3和nums4，数组长度都是n，请你计算有多少个元组(i, j, k, l)能满足：
0 <= i, j, k, l < nnums1[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
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int result=0;
HashMap<Integer,Integer> map =new HashMap<Integer,Integer>();
for(int i:nums1){
for(int j:nums2){
int temp=i+j;
if(map.containsKey(temp)){
int num=map.getOrDefault(temp,0);
map.put(temp,num+1);
}else{
map.put(temp,1);
}
}
}
for(int i:nums3){
for(int j:nums4){
int temp=i+j;
if(map.containsKey(0-temp)){
result+=map.getOrDefault(0-temp,0);
}
}
}
return result;
}
}就是把四个数组变成两个数组，然后就把问题转化成了两数之和的问题，要注意的是Key依然存的是元素的值，但是Value不再是存索引，而是出现Key对应元素的次数，看完老师的码我发现我铸币了，我都用getOrDefault()了，根本就不需要先一步进行containsKey（）判断
class Solution {
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
int res = 0;
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
//统计两个数组中的元素之和，同时统计出现的次数，放入map
for (int i : nums1) {
for (int j : nums2) {
int sum = i + j;
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
}
//统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
for (int i : nums3) {
for (int j : nums4) {
res += map.getOrDefault(0 - i - j, 0);
}
}
return res;
}
}这是老师写的
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
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] hash=new int[26];
for(int i=0;i<ransomNote.length();i++){
hash[ransomNote.charAt(i)-'a']++;
}
for(int i=0;i<magazine.length();i++){
hash[magazine.charAt(i)-'a']--;
}
for(int i=0;i<26;i++){
if(hash[i]>0){
return false;
}
}
return true;
}
}昨天的字母异位词的拓展题里面已经做了一遍，两题思路一样，最后改下判断就行
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] 。 注意，输出的顺序和三元组的顺序并不重要。示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
不信邪自己先写了哈希法，最后去重的操作直接搞不成功，白白浪费两个小时
哈希法
下面是老师的哈希法
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
// 如果第一个元素大于零，不可能凑成三元组
if (nums[i] > 0) {
return result;
}
// 三元组元素a去重
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
HashSet<Integer> set = new HashSet<>();
for (int j = i + 1; j < nums.length; j++) {
// 三元组元素b去重
if (j > i + 2 && nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2]) {
continue;
}
int c = -nums[i] - nums[j];
if (set.contains(c)) {
result.add(Arrays.asList(nums[i], nums[j], c));
set.remove(c); // 三元组元素c去重
} else {
set.add(nums[j]);
}
}
}
return result;
}
}我去我去，我怎么就没有想到给数组先排序呢，先排序去重只需要相邻元素相等直接跳过就行，直接解决了去重的问题，但是还是好难理解啊，直接看双指针的讲解了
双指针法
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
// 找出a + b + c = 0
// a = nums[i], b = nums[left], c = nums[right]
for (int i = 0; i < nums.length; i++) {
// 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
if (nums[i] > 0) {
return result;
}
if (i > 0 && nums[i] == nums[i - 1]) { // 去重a
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (right > left) {
int sum = nums[i] + nums[left] + nums[right];
if (sum > 0) {
right--;
} else if (sum < 0) {
left++;
} else {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
return result;
}
}太巧妙了，第一个数用循环遍历，第二个数和第三个数用双指针，一个left指针往右边跑找第二个数，一个right指针往左跑找第三个数，到left=right终止，去重也只需要判断相邻是否相等就行，但是要特别注意因为一开始i和left是紧挨着的，所以如果用nums[i] == nums[i+1]来判断去重，就会把三元组前两个元素（即i和left对应的元素）相同的情况给错删了，得用nums[i] == nums[i - 1]才行
18. 四数之和
给你一个由
n个整数组成的数组nums，和一个目标值target。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target你可以按 任意顺序 返回答案 。
示例 1：
输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2：
输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]
import java.util.*;
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums); // 排序数组
List<List<Integer>> result = new ArrayList<>(); // 结果集
for (int k = 0; k < nums.length; k++) {
// 剪枝处理
if (nums[k] > target && nums[k] >= 0) {
break; // 此处的break可以等价于return result;
}
// 对nums[k]去重
if (k > 0 && nums[k] == nums[k - 1]) {
continue;
}
for (int i = k + 1; i < nums.length; i++) {
// 第二级剪枝
if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
break; // 注意是break到上一级for循环，如果直接return result;会有遗漏
}
// 对nums[i]去重
if (i > k + 1 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.length - 1;
while (right > left) {
long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
if (sum > target) {
right--;
} else if (sum < target) {
left++;
} else {
result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
// 对nums[left]和nums[right]去重
while (right > left && nums[right] == nums[right - 1]) right--;
while (right > left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
}
return result;
}就是在三数之和外面再套一层循环
总结
什么时候用哈希法
当题目很明确查找元素是否存在的时候，
范围小且确定用数组，比如赎金信，字母异位词
范围大不确定用set，比如两个数组的交集如果输入值的范围没有改小或者说数据比较分散，这时候用数组就会浪费很多空间了
查找成对的元素用Map，KV键值对，比如两数之和需要知道查找数和对应的索引
什么时候哈希法用起来很复杂不推荐用
查找元素是否存在，但是有着明确的去重要求，推荐考虑双指针，比如三数之和、四数之和
有“AI”的1024 = 2048，欢迎大家加入2048 AI社区
更多推荐
8
0- 0
已为社区贡献1条内容
所有评论(0)