:::tips 作者：LemonCat🐱
时间：2023-8-1 :::

第三章 - 哈希表 part01

:::info

  • 哈希表理论基础
  • 242.有效的字母异位词
  • 349.两个数组的交集
  • 202.快乐数

  • 1.两数之和 :::

    理论基础

  • 建议：大家要了解哈希表的内部实现原理，哈希函数，哈希碰撞

  • 什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。
  • 这句话很重要，大家在做哈希表题目都要思考这句话。

  • 文章讲解：代码随想录 (programmercarl.com)

    常见的三种哈希结构

  • 数组

  • set - 集合
  • map - 映射

    242.有效的字母异位词

    建议： 这道题目，大家可以感受到 数组 用来做哈希表 给我们带来的遍历之处。 题目链接：242. 有效的字母异位词 - 力扣（LeetCode） 文章讲解/视频讲解：代码随想录 (programmercarl.com)

方法一 - 哈希表法 - 数组

这个题可以取巧 - 因为字符的范围是小写字母，所以可以用数组当哈希表，minuscule[ch - 'a'] 表示字符 ch 的出现次数，这样做更加省时间省内存

  1. 暴力解法：两层 for 循环，同时记录字符是否重复出现
  2. 哈希表法：
    1. 定义一个数组 minuscule 用来上记录字符串 s 里字符出现的次数
    2. 把字符映射到数组也就是哈希表的索引下标上
      1. 映射 minuscule[s.charAt(i) - 'a']
      2. 因为字符 a 到字符 z 的 ASCII 是 26 个连续的数值，所以字符 a 映射为下标 0，相应的字符 z 映射为下标 25
    3. 遍历 字符串 s 将出现元素 +1 -> 这样就将字符串 s 中字符出现的次数，统计出来了。
    4. 遍历 字符串 t 将出现元素 -1
    5. 最后检查 minuscule 数组
      1. 如果有元素不为零 0，说明字符串 s 和 t 一定是谁多了字符或者谁少了字符 -> 不符合异位词 return false
      2. 若全为零 则是异位词 return true
  1. /**
  2.  * 方法一 - 哈希表法
  3.  */
  4. class Solution {
  5.     public boolean isAnagram(String s, String t) {
  7.         // 小写字母哈希表
  8.         int[] minuscule = new int[26];
  10.         // 遍历 s 字符串 将对的字符出现的个数 记录数组中（+）
  11.         for (int i = 0; i < s.length(); i++) {
  12.             minuscule[s.charAt(i) - 'a']++; // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
  13.         }
  15.         // 遍历 t 字符串 将对的字符出现的个数 记录数组中（-）
  16.         for (int j = 0; j < t.length(); j++) {
  17.             minuscule[t.charAt(j) - 'a']--;
  18.         }
  19.         for (int k : minuscule) {
  20.             if (k != 0) {
  21.                 return false;// minuscule 数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
  22.             }
  23.         }
  25.         return true; // minuscule 数组所有元素都为零0，说明字符串s和t是字母异位词
  26.     }
  27. }
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

349. 两个数组的交集

建议：本题就开始考虑 什么时候用 set 什么时候用数组，本题其实是使用 set 的好题 但是后来力扣改了题目描述和 测试用例，添加了 0 <= nums1[i], nums2[i] <= 1000 条件，所以使用数组也可以了，不过建议大家忽略这个条件。 尝试去使用 set。 题目链接：349. 两个数组的交集 - 力扣（LeetCode） 文章讲解/视频讲解：代码随想录 (programmercarl.com)

思路

  • 输出结果中的每个元素一定是唯一的 -> 结果是去重的， 同时可以不考虑输出结果的顺序 -> 用 set 集合会更好一点
  • 题目描述中数值范围比较小 -> 用数组解决更好一点
  1. 双 set
    1. 优点：自动帮助我们去重；在数据量较大时 更节省空间
    2. 缺点：直接使用 set 不仅占用空间比数组大，而且速度要比数组慢
  2. 双数组
    1. 优点：由于题中数值范围较小 -> 用数组速度会更快
    2. 缺点：面对数据量较大 或 数据跨度较大（稀疏矩阵）-> 占用空间较大

方法一 - 双 set

  1. 用一个哈希集合存放一个数组中的元素，会自动去重。
  2. 遍历另一个数组，当访问到的元素出现在哈希集合中时 -> 将其放到结果集中 resSet
  3. 将 resSet 集合 -> arr 数组
  1. /**
  2.  * 方法一 - 两个 set + 一个数组
  3.  */
  4. class Solution {
  5.     public int[] intersection(int[] nums1, int[] nums2) {
  7.         // 若两个数组传入的有一个是 null -> 提前返回
  8.         if (nums1 == null || nums2 == null) {
  9.             return null;
  10.         }
  12.         Set<Integer> hashSet = new HashSet<>(); // Hash 表
  13.         Set<Integer> resSet = new HashSet<>(); // 结果集
  15.         // 将nums中的值 存储到 hashSet 中
  16.         for (int n1 : nums1) {
  17.             hashSet.add(n1);
  18.         }
  20.         // 将nums2中的值 与 hashSet 中的值作比较 若存在则放到结果集 resSet 中（可以帮我们自动去重）
  21.         for (int n2 : nums2) {
  22.             if (hashSet.contains(n2)) {
  23.                 resSet.add(n2);
  24.             }
  25.         }
  28.         // 将 set 转换成数组
  29.         int[] arr = new int[resSet.size()];
  31.         int j = 0;
  32.         for (Object o : resSet) {
  33.             arr[j++] = (int) o;
  34.         }
  36.         return arr;
  37.     }
  38. }

改进

  • 将 set 转换成数组
  • 原来的写法
  1. int[] arr = new int[resSet.size()];
  3. int j = 0;
  4. for (Object o : resSet) {
  5.     arr[j++] = (int) o;
  6. }
  • 更优雅的写法
    • 具体详情以后有时间在研究
  1. int[] arr = resSet.stream().mapToInt(x -> x).toArray();

方法二 - 双数组

  1. /**
  2.  * 方法二 - 双数组
  3.  */
  5. class Solution {
  6.     public int[] intersection(int[] nums1, int[] nums2) {
  8.         // 若两个数组传入的有一个是 null -> 提前返回
  9.         if (nums1 == null || nums2 == null) {
  10.             return null;
  11.         }
  13.         int[] hashArr = new int[1001]; // Hash 表
  14.         int[] resArr; // 结束数组
  16.         // 遍历 num1 将其放到对应的hash表中
  17.         for (int i : nums1) {
  18.             hashArr[i]++;
  19.         }
  21.         // 遍历 num2 若发现便利的对象在hash表中已经存在了 证明是交集 -> 存入结果集中
  22.         Set<Integer> resSet = new HashSet<>();
  23.         for (int j : nums2) {
  24.             if (hashArr[j] != 0) {
  25.                 resSet.add(j);
  26.             }
  27.         }
  28.         resArr = new int[resSet.size()];
  30.         // 将结果集 -> 转换成 数组
  31.         int j = 0;
  32.         for (Integer res : resSet) {
  33.             resArr[j++] = (int) res;
  34.         }
  35.         return resArr;
  36.     }
  37. }

202. 快乐数

建议：这道题目也是 set 的应用，其实和上一题差不多，就是套在快乐数一个壳子 题目链接：202. 快乐数 - 力扣（LeetCode） 文章讲解：代码随想录 (programmercarl.com)

方法 - set 集合

  • 有限大小的整数都可以在有限次数的替换运算中压缩到有限位数，所以如果不是快乐数一定会出现循环
  • 那么对一个数不断做迭代替换过程中如果出现了不在 1 处的循环则一定不是快乐数
  • 所以用 Set 存放过程中所有的状态
    • 每次替换就在这个 Set 中查询是否到达过，如果到达过则返回 false
  1. /**
  2.  * 方法 - set 集合
  3.  */
  4. class Solution {
  5.     public boolean isHappy(int n) {
  6.         Set<Integer> hashSet = new HashSet<>(); // 记录每次平方和结果集
  7.         while (true) {
  9.             int res = 0; // 每次平方和
  10.             int[] arrN = getNum(n); // 传入数 返回数每一位数组成的数组
  12.             // 计算每个数平方后的和
  13.             for (int i : arrN) {
  14.                 res += i * i;
  15.             }
  17.             // 如果结果是 1 就是快乐数
  18.             if (res == 1) {
  19.                 return true;
  20.             }
  22.             // 结果集中存在 结束 -> 发生重复 -> 不是快乐数
  23.             if (hashSet.contains(res)) {
  24.                 return false;
  25.             }
  27.             hashSet.add(res); 
  28.             n = res;
  30.         }
  31.     }
  33.     /**
  34.      * 传入数 返回数每一位数组成的数组
  35.      *
  36.      * @param n
  37.      * @return
  38.      */
  39.     int[] getNum(int n) {
  41.         int length = ((Integer) n).toString().length(); // 获取位数的长度
  43.         int[] arrN = new int[length]; // 返回的数组
  45.         for (int i = 0; i < length; i++) {
  46.             arrN[i] = n % 10;
  47.             n /= 10;
  48.         }
  49.         return arrN;
  50.     }
  51. }

1. 两数之和

建议：本题虽然是 力扣第一题，但是还是挺难的，也是 代码随想录中 数组，set 之后，使用 map 解决哈希问题的第一题。建议大家先看视频讲解，然后尝试自己写代码，在看文章讲解，加深印象。 题目链接 1. 两数之和 - 力扣（LeetCode） 文章讲解/视频讲解：代码随想录 (programmercarl.com)

思路

  1. 访问到一个数 nums[i]，与之和为 target 的数只能是 target-nums[i]
  2. 将每次便利的数存入 Map 中
    • 注意：K-V 分别对应的值！！！
      • K：数值
      • V：索引
    • 因为我们最终是要找对应数值的索引 -> arr[1] = map.get(target - nums[i])
  3. 然后找 target-nums[i] 是否在 Map 中出现过 -> 将当前索引 和 将找到的 数值对应的 V 存入数组
  4. 返回数组~

方法一 - Map 方法

  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  4.         HashMap<Integer, Integer> map = new HashMap<>();
  5.         int[] arr = new int[2];
  7.         if (nums == null || nums.length == 0) {
  8.             return arr;
  9.         }
  11.         // K - V
  12.         // K：数值
  13.         // V：索引
  14.         for (int i = 0; i < nums.length; i++) {
  16.             // 遍历当前元素，并在map中寻找是否有匹配的key
  17.             if (map.containsKey(target - nums[i])) {
  18.                 arr[0] = i;
  19.                 arr[1] = map.get(target - nums[i]);
  20.                 return arr;
  21.             }
  23.             // 如果没找到匹配对，就把访问过的元素和下标加入到map中
  24.             map.put(nums[i], i);
  25.         }
  26.         return arr;
  27.     }
  28. }

第三章 - 哈希表 part02

:::info

  • 454.四数相加II
  • 383.赎金信
  • 15.三数之和
  • 18.四数之和
  • 总结
    :::

454.四数相加II

建议：本题是 使用map 巧妙解决的问题，好好体会一下 哈希法 如何提高程序执行效率，降低时间复杂度，当然使用哈希法 会提高空间复杂度，但一般来说我们都是舍空间 换时间， 工业开发也是这样。 题目链接：454. 四数相加 II - 力扣（LeetCode） 文章讲解/视频讲解：代码随想录

思路

如果 暴力解 嵌套四层循环做这个题时间复杂度太高，需要 O(n4)
而我们采用下面的方法只需要 O(n2)

  1. 首先定义一个 HashMap
    1. key -> 两数之和
    2. value -> 两数之和出现的次数
  2. 定义 count，用来统计 a+b+c+d = 0 出现的次数。
  3. 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
  4. 遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话
    1. 用 count 把 map 中 key 对应的value也就是出现次数统计出来。
  5. 最后返回统计值 count 就可以了

为什不能把第一个单独放在一起，后三个放一起？

  • 这样时间复杂度还是太高，O(n3)

    方法 - Map

    1. /**
    2. * 方法 - Map
    3. */
    4. class Solution {
    5.   public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
    7.       Map<Integer, Integer> map = new HashMap<>();
    8.       int count = 0; // a+b+c+d=0 的个数
    10.       // 统计 num1 与 num2 两个数组中的元素之和是相同的出现的次数
    11.       for (int i : nums1) {
    12.           for (int j : nums2) {
    13.               // getOrDefault方法，查询参数是Key - getOrDefault(Object key, V defaultValue)
    14.               // 如果查的到，返回的是对应的 value
    15.               // 如果查询不到，就返回默认值 defaultValue
    16.               map.put(i + j, map.getOrDefault(i + j, 0) + 1);
    17.           }
    18.       }
    20.       // 统计剩余的两个数组中元素的的和 (i + j) 为num3和num4数组组成元素的和
    21.       // 在map中找是否存在 Key 为 0 - (i + j) 的情况，同时记录次数
    22.       for (int i : nums3) {
    23.           for (int j : nums4) {
    24.               count += map.getOrDefault(-(i + j), 0);
    25.           }
    26.       }
    28.       return count;
    29.   }
    30. }

383.赎金信

建议：本题 和 242.有效的字母异位词 是一个思路 ，算是拓展题 题目链接：力扣 383. 赎金信 文章讲解：代码随想录

方法一 - 暴力法

  • 两层for循环，不断去寻找
  • 找到一个就记录一次 最后匹配找到的个数是否与 ransomNote 字符串长度相等 若相当 -> true
    • 注意1：找到后要退出循环 - 否则会继续对比下去 就会变成 1 对 多的关系
    • 注意2：需要一个magazine大小的数组 用于存 magazine 已经匹配成功的字符 ```java /**

  • 方法一 - 暴力解 */ class Solution { public boolean canConstruct(String ransomNote, String magazine) {

    1.   int[] useArr = new int[magazine.length()]; // 定义一个书畅读为 magazine 长度的数组
    2.   int count = 0; // 记录成功匹配的次数
    4.   for (int i = 0; i < ransomNote.length(); i++) {
    5.       for (int j = 0; j < magazine.length(); j++) {
    6.           // 如果当前 ransomNote 字符 与 magazine 字符相等 并且 不是我们之前在magazine匹配过的字符
    7.           if (ransomNote.charAt(i) == magazine.charAt(j) && useArr[j] == 0) {
    8.               count++; // 匹配成功 次数+1
    9.               useArr[j] = magazine.charAt(j); // 并将成功匹配的字符存在对应索引的位置
    10.               break; // 一定要退出循环！！！ 否则会继续对比下去 就会变成 1 对 多的关系
    11.           }
    13.       }
    14.   }
    15.   return count == ransomNote.length();

    } } ```

    方法二 - 哈希法

  1. 因为题目所只有小写字母，那可以采用空间换取时间的哈希策略，
    1. 用一个长度为26的数组 int[] record = new int[26]
    2. 记录 magazine 里字母出现的次数 record[ransomNote.charAt(i) - 'a']++
  2. 然后再用ransomNote去验证这个数组是否包含了 ransomNote所需要的所有字母
    1. record[magazine.charAt(i) - 'a']-- ```java /**

  • 方法二 - 哈希法 */ class Solution { public boolean canConstruct(String ransomNote, String magazine) {

    1.   // 如果前>后直接返回
    2.   if (ransomNote.length() > magazine.length()) {
    3.       return false;
    4.   }
    6.   // 定义一个哈希映射数组
    7.   int[] record = new int[26];
    9.   // 将 randomNote 中的字符 映射到数组中 ++ 
    10.   for (int i = 0; i < ransomNote.length(); i++) {
    11.       record[ransomNote.charAt(i) - 'a']++;
    12.   }
    13.   // 将 magazine 中的字符 映射到数组中 --
    14.   for (int i = 0; i < magazine.length(); i++) {
    15.       record[magazine.charAt(i) - 'a']--;
    16.   }
    18.   // 如果大于零说明 ransomNote 里出现的字符 magazine没有
    19.   for (int a : record) {
    20.       if (a > 0) {
    21.           return false;
    22.       }
    23.   }
    24.   return true;

    } } ```

  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

注意：

  1. 为什么不直接用map？
  2. 其实在本题的情况下，使用map的空间消耗要比数组大一些的，
    1. 因为map要维护红黑树或者哈希表，而且还要做哈希函数，是费时的！
    2. 数据量大的话就能体现出来差别了。 所以数组更加简单直接有效！

      15.三数之和

      建议：本题虽然和 两数之和 很像，也能用哈希法，但用哈希法会很麻烦，双指针法才是正解，可以先看视频理解一下 双指针法的思路，文章中讲解的，没问题 哈希法很麻烦。 题目链接：力扣 15. 三数之和 文章讲解/视频讲解：代码随想录

方法一 - 排序 + 双指针

  • 难点：结果需要去重

代码随想录 | 第三章 - 哈希表 - 图1

  1. 对数组进行排序 -> 方便后面双指针进行操作
  2. for 循环遍历
    1. i从下标0的地方开始
    2. 定义指针 left 在 i+1 的位置上
    3. 定义指针 right 在数组结尾的位置上 -> nums.length - 1
  3. a = nums[i]，b = nums[left]，c = nums[right] 找出 a + b + c = 0

  4. left 和 right 指针的移动 -> 注意数组是排序过后的

    1. nums[i] + nums[left] + nums[right] > 0 -> 三数之和大了，right下标就应该向左移动，使得三数之和小一些
    2. nums[i] + nums[left] + nums[right] < 0 -> 三数之和小了，left下标就应该向右移动，使得三数之和大一些

      去重逻辑

      a 的去重:
      1. if (i > 0 && nums[i] == nums[i - 1]) {
      2. continue;
      3. }

  5. i > 0 即去除了第一个元素情况

    • 当 i = 0时 若进行 i - 1 就直接 NPE
    • 并且 i = 0 由于是第一个不可能有所谓重复出现

  6. 使用nums[i] == nums[i - 1] 而不是 nums[i] == nums[i + 1]

    1. 若使用后者三元组中出现重复元素的情况直接pass掉了
    2. 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断 下一个也是-1，那这组数据就pass了。
    3. 题目中要求的是 -> 组合不能有重复 而不是组合内部不能有重复
      b 和 c 的去重：

  7. 原理同 a 去重

  8. 注意放置位置 -> 去重逻辑应该放在找到一个三元组之后
    1. 否则第一次出现的可能也被干掉了~
      1. while (right > left && nums[right] == nums[right - 1]) right--;
      2. while (right > left && nums[left] == nums[left + 1]) left++;

Code

  1. /**
  2. * 排序 + 双指针
  3. */
  4. class Solution {
  5.     public List<List<Integer>> threeSum(int[] nums) {
  7.         List<List<Integer>> lists = new ArrayList<>(); // 用于返回的二维集合
  9.         // 先对数组内容进行排序
  10.         Arrays.sort(nums);
  12.         int left;
  13.         int right;
  14.         int sum;
  16.         // 找出a + b + c = 0
  17.         // a = nums[i], b = nums[left], c = nums[right]
  18.         for (int i = 0; i < nums.length - 2; i++) {
  20.             if (nums[i] > 0) { // 若排序后第一个元素都大于0 就直接返回
  21.                 return lists;
  22.             }
  23.             left = i + 1;
  24.             right = nums.length - 1;
  26.             // 对a去重
  27.             // 1. i > 0 即除了第一个元素情况
  28.             // 2. 对比当前元素和前一个元素 相等则说明 a 重复
  29.             // 3. 不能用当前元素比较后一个元素 -> 题目中要求的是组合不能有重复 而不是组合内不不能有重复
  30.             if (i > 0 && nums[i] == nums[i - 1]) {
  31.                 continue;
  32.             }
  34.             while (left < right) {
  35.                 sum = nums[i] + nums[left] + nums[right];
  36.                 if (sum < 0) {
  37.                     left++;
  38.                 } else if (sum > 0) {
  39.                     right--;
  40.                 } else {
  41.                     lists.add(Arrays.asList(nums[i], nums[left], nums[right]));
  42.                     // 去重逻辑应该放在找到一个三元组之后 分别对b 和 对c去重
  43.                     while (right > left && nums[right] == nums[right - 1]) right--;
  44.                     while (right > left && nums[left] == nums[left + 1]) left++;
  46.                     // 指针移动
  47.                     right--;
  48.                     left++;
  49.                 }
  50.             }
  52.         }
  54.         return lists;
  55.     }
  56. }

方法二 - 哈希法（不推荐）

  • 以后有时间补充 -> 去重的过程不好处理 👻

18.四数之和

建议： 要比较一下，本题和 454.四数相加II 的区别，为什么 454.四数相加II 会简单很多，这个想明白了，对本题理解就深刻了。 本题 思路整体和 三数之和一样的，都是双指针，但写的时候 有很多小细节，需要注意，建议先看视频。 题目链接：力扣 18. 四数之和 文章讲解/视频讲解：代码随想录

方法 - 双层循环 + 双指针

  • 整体思路与三数之和保持一致
    • 四数之和 = 三数之和 + for循环
  1. 剪枝：剪枝操作不能直接套之前的 三数之和
    1. 分为 一级剪枝 和 二级剪枝
      1. 剪枝一定要注意 只有 target > 0 才能剪枝 负数减不了
      2. 二级剪枝时 不能直接像一级剪枝一样直接返回 -> 应该 break
        只是当前组合不成立了，还有每遍历到到的组合！！！
    2. 剪枝过程更细腻 需要注意所比较的数值是谁
  2. 去重：整体思路与三数之和相同
    1. 区别在于去重逻辑多一个数
  1. class Solution {
  2.     public List<List<Integer>> fourSum(int[] nums, int target) {
  4.         List<List<Integer>> lists = new ArrayList<>(); // 用于返回的二维集合
  6.         // 先对数组内容进行排序
  7.         Arrays.sort(nums);
  9.         int left;
  10.         int right;
  11.         long sum; // int 在后面求和会溢出
  13.         // 找出a + b + c + d = target
  14.         // a = nums[j] b = nums[i], c = nums[left], d = nums[right]
  16.         for (int j = 0; j < nums.length - 3; j++) {
  18.             // 一级剪枝 - 注意一定是大于 0 才能剪枝 否则若 target = -4  nums[j] = -3 时不能剪枝 后面可能有 -1
  19.             if (target > 0 && nums[j] > target) {
  20.                 return lists;
  21.             }
  22.             // 对 a 去重
  23.             if (j > 0 && nums[j] == nums[j - 1]) {
  24.                 continue;
  25.             }
  26.             for (int i = j + 1; i < nums.length - 2; i++) {
  28.                 // 二级剪枝 - 同一级剪枝
  29.                 if (target > 0 && nums[j] + nums[i] > target) {
  30.                     break; // 这个地方一定是 break 不能是 return 因为后面还有没遍历的呢 你给返回就GG了
  31.                 }
  33.                 // 对 b 去重
  34.                 if (i > j + 1 && nums[i] == nums[i - 1]) {
  35.                     continue;
  36.                 }
  38.                 left = i + 1;
  39.                 right = nums.length - 1;
  41.                 while (left < right) {
  42.                     sum = (long) nums[j] + nums[i] + nums[left] + nums[right];
  43.                     if (sum < target) {
  44.                         left++;
  45.                     } else if (sum > target) {
  46.                         right--;
  47.                     } else {
  48.                         lists.add(Arrays.asList(nums[j], nums[i], nums[left], nums[right]));
  49.                         // 去重逻辑应该放在找到一个三元组之后 分别 对c 和 对d 去重
  50.                         while (right > left && nums[right] == nums[right - 1]) right--;
  51.                         while (right > left && nums[left] == nums[left + 1]) left++;
  53.                         // 指针移动
  54.                         right--;
  55.                         left++;
  56.                     }
  57.                 }
  59.             }
  60.         }
  63.         return lists;
  64.     }
  65. }
  • 恰饭~