代码随想录刷题总结--哈希篇

总结

1. 题中为某个元素出现的次数等意思，考虑使用哈希法

2. 哈希表实际操作一般由三类，数组，元素有限且数量较小的情况使用，set，可以去重，数量大不确定适用，map适用于key：vaule的结构

242.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

思路

1. 根据题意可以解释为两个单词组成的字母相同，但顺序可能不同的则为true

2. 可以使用暴力循环，同时解析为一个单词中的字母在另一个单词中的出现，考虑使用哈希法

3. 新建一个数组作为哈希表，下标为出现过的单词，值为出现的频率

  public boolean isAnagram(String s, String t) {
         //1.新建数组，作为hash表，
         int[] ints = new int[26];
         //2.遍历第一个字符串，记录出现过的字母和频率
         for (int i = 0; i < s.length(); i++) {
             ints[s.charAt(i)] += 1;
         }
         //3.遍历第二个字符，当数组对应下标的字符出现，则频率减一
         for (int i = 0; i < t.length(); i++) {
             ints[t.charAt(i)] -= 1;
         }
         //4.遍历数组，如果数组有哪个下标的值没有为0，说明两个字符串中的字符没有抵消掉，则它们组成的字符不一样
         for (int i = 0; i < ints.length; i++) {
             if (ints[i] != 0){
                 return false;
             }
             
         }
         return true;
     }

349. 两个数组的交集

思路

1. 可以理解为某一个元素同时出现在两个数组中，

2. 数组长度不确定，使用set作为哈希表处理

  public int[] intersection(int[] nums1, int[] nums2) {
         //1.新建2个set，分别映射两个数组
         HashSet<Integer> set = new HashSet<>();
         HashSet<Integer> set1 = new HashSet<>();
         //2.开始遍历一个数组，将元素映射到set1
         for (int i : nums1) {
             set.add(i);
         }
         //3.遍历第二个数组，并且当第一个set中的元素出现过则加入第二个set中
         for (int i : nums2) {
             if (set.contains(i)){
                 set1.add(i);
             }
         }
         //第二个set即为交集
         return set1.stream().mapToInt(x -> x).toArray();   
     }

第202题. 快乐数

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：19 输出：true 解释： 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1

思路：

1. 根据题意中，有一个重要的点，当非快乐数，可能存在每次处理后得到相同的结果，并形成无限循环状态，因此需要考虑处理循环场景‘

2. 形成循环，说明处理结果已经出现过，因此可以理解为处理结果出现的次数问题

3. 使用set作为哈希表，处理每次的结果，当出现过一样的值，则为非快乐数

  public boolean isHappy(int n) {
         //1.新建一个set，映射每次处理的结果
         HashSet<Integer> set = new HashSet<>();
         //2.开始循环处理 快乐数的规则,当处理结果不为1且没有重复出现的时候循环处理
         while (!set.contains(n) && n != 1){
             set.add(n);
             //按照题意处理
             n = doSome(n);
         }
         //循环结束则判断是否为快乐数
         return n == 1;
     }
 ?
     private int doSome(int n) {
         //和
         int sum = 0;
         while (sum > 0){
             //取模获取末尾数字
             int num1 = n % 10;
             sum += num1 * num1;
             //取第一个商获取前面的数组
             n = n / 10;
         }
         return n;
         
     }

1. 两数之和

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

思路

1. 寻找给定数组中的是否能相加得到给定和，理解为数组中的元素，对于的给定和减去该元素得到的数字，是否在数组中出现，考虑使用hash表

2. 题意需要返回下标，因此在hash‘映射中不仅要存储下标，还要存储值，考虑使用map，使用key为值，value为下标

  public int[] twoSum(int[] nums, int target) {
         //定义一个数组作为返回 0下标第一个符合下标值 1下标为数组的第二个下标
         int[] ints = new int[2];
         if(nums == null || nums.length == 0){
             return ints;
         }
         Map<Integer,Integer> map = new HashMap<>();
         //变量数组
         for (int i = 0; i < nums.length; i++) {
             //定义一个临时值为 目标和减去当前数字的值 ，用于查询映射的map中是否存在该值，存在则符合条件
             int temp = target - nums[i];
             if (map.containsKey(temp)) {
                 //存在符合条件的值
                 //组装数组 ,第0个元素下标w为当前下标 ，第二个根据map中的映射获取
                 ints[0] = i;
                 ints[1] = map.get(temp);
                 break;
             }
             //没有匹配到 则组装map数据
             map.put(nums[i],i);
 ?
         }
         return ints;
     }

第454题.四数相加II

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

思路：

1. 首先定义 一个map，key放a和b两数之和，value 放a和b两数之和出现的次数。

2. 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。

3. 定义int变量count，用来统计 a+b+c+d = 0 出现的次数。

4. 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。

5. 最后返回统计值 count 就可以了

 ?
     public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
         Map<Integer,Integer> map = new HashMap<>();
         int count = 0;
         for (int i : nums1) {
             for (int i1 : nums2) {
                 int sum = i + i1;
                 //getOrDefault方法可以获取map，两个数之和出现的次数，没有出现过则为0，每一次次数加一
                 map.put(sum,map.getOrDefault(sum,0) + 1);
             }
         }
         for (int i : nums3) {
             for (int i1 : nums4) {
                 //统计加和的是否有为0 的元组，有则增加 次数
                 count += map.getOrDefault(-i - i1,0);
             }
         }
         return count;
     }

383. 赎金信

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

思路

1. 可以理解为一个字符串的字符是否全部在另一个字符串中出现过，考虑用哈希表

2. 只用返回boolea，字符串中的字符固定，就是26个，可以新建一个数组作为哈希表

3. 数组下标为对应字符，值为出现的频率

4. 当第一个字符串的字符出现过，字符对应的下标频率，加一

5. 第二个字符串出现的字符出现的，字符对应的下标减一

6. 最终查询数组中是否有负值即可比较

     public boolean canConstruct(String ransomNote, String magazine) {
         // shortcut
         if (ransomNote.length() > magazine.length()) {
             return false;
         }
         // 定义一个哈希映射数组
         int[] record = new int[26];
 ?
         // 遍历
         for(char c : magazine.toCharArray()){
             record[c - 'a'] += 1;
         }
 ?
         for(char c : ransomNote.toCharArray()){
             record[c - 'a'] -= 1;
         }
         
         // 如果数组中存在负数，说明ransomNote字符串总存在magazine中没有的字符
         for(int i : record){
             if(i < 0){
                 return false;
             }
         }
         return true;
     }

第15题. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意： 答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]

思路

1. 使用双指针方法，指定首尾两个指针，遍历数组，首先进行排序，

2. 当前值和首尾指针的和大于目标值，则移动尾指针向前，整体变小

3. 小于目标值移动前指针，整体变大

4. 找到目标组合，则放入返回中

5. 去重需要和当前元素的前一个元素去重

  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;
     }
 }