代码随想录 算法训练 Day6：哈希表part1

简介

先介绍一些基本概念。

什么是哈希表？

哈希表​​：一种通过哈希函数将键（key）映射到存储位置的数据结构（我理解是一种思想）。

哈希函数​​：一种将任意长度的输入（如字符串、文件）转换为固定长度输出（通常为数字）的算法，比如我们生活中常见的md5算法。这个固定长度的输出叫做哈希值。

哈希表大小：​​​​是底层数组的固定容量，用于限定键值对的存储位置范围（通过 hash % size 计算下标）。

---

哈希表如何使用？

举个例子，比如我们现在要实现一个姓名，年龄的哈希表，在这个表中存储25岁的Alice这条数据。

​​步骤1：计算哈希值​​

• 哈希表调用一个​​哈希函数​​，把键 "Alice" 转换成数字（比如 1638）。
  （就像把名字变成员工ID，方便管理）

​​步骤2：计算存储位置​​

• 假设哈希表内部有 ​​10 个格子​​（数组），用 哈希值 % 10 决定存到哪个格子：
  1638 % 10 = 8 → 存到 ​​格子8​​。

​​步骤3：实际存储​​

• 格子8 原来是空的，直接存入 {"Alice": 25}。
  （像把文件放进编号8的档案柜）

 此时哈希表内部结构​​：

[0]: 空  
[1]: 空  
...  
[8]: {"Alice": 25}  ← 数据在这里！  
[9]: 空

好的！我用 ​​存 "Alice": 25​​ 这个例子，一步步拆解哈希表如何工作，保证你秒懂！

---

​​2. 如果发生冲突？（比如 "Bob" 也存到格子8）​​

​​场景​​

• 假设 "Bob" 的哈希值是 2588 → 2588 % 10 = 8，也要存到格子8。

​​解决方法​​

• ​​拉链法​​：格子8 挂一个链表，按顺序存 {"Alice": 25} 和 {"Bob": 30}。
  （像档案柜8里放两个文件夹，标签分别是Alice和Bob）

• ​​线性探测法​​：8→9→10→... 直到找到空位

​​此时结构​​

# 拉链法
[0]: 空  
[1]: 空  
...  
[8]: ["Alice":25] → ["Bob":30]
[9]: 空# 线性探测法
[0]: 空  
[1]: 空  
...  
[8]: ["Alice":25] 
[9]: ["Bob":30]

题目

242.有效的字母异位词

建议： 这道题目，大家可以感受到 数组 用来做哈希表 给我们带来的遍历之处。

力扣题目链接(opens new window)

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词（即 s 和 t 包含的字符种类和数量完全相同，但顺序可以不同）。

示例 1: 输入: s = "anagram", t = "nagaram" 输出: true

示例 2: 输入: s = "rat", t = "car" 输出: false

说明: 你可以假设字符串只包含小写字母。

题目链接/文章讲解/视频讲解： https://programmercarl.com/0242.有效的字母异位词.html

349. 两个数组的交集

建议：本题就开始考虑 什么时候用set 什么时候用数组，本题其实是使用set的好题，但是后来力扣改了题目描述和 测试用例，添加了 0 <= nums1[i], nums2[i] <= 1000 条件，所以使用数组也可以了，不过建议大家忽略这个条件。 尝试去使用set。

给定两个数组 nums1 和 nums2 ，返回 它们的 交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

说明： 输出结果中的每个元素一定是唯一的。 我们可以不考虑输出结果的顺序。

题目链接/文章讲解/视频讲解：https://programmercarl.com/0349.两个数组的交集.html

202. 快乐数

建议：这道题目也是set的应用，其实和上一题差不多，就是 套在快乐数一个壳子

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

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

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

• 1 <= n <= 2的31次方 - 1

题目链接/文章讲解：https://programmercarl.com/0202.快乐数.html

1. 两数之和

建议：本题虽然是 力扣第一题，但是还是挺难的，也是 代码随想录中 数组，set之后，使用map解决哈希问题的第一题。

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

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• 109 <= nums[i] <= 109
• 109 <= target <= 109
• 只会存在一个有效答案

题目链接/文章讲解/视频讲解：https://programmercarl.com/0001.两数之和.html

答案

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.Arrays;
import java.util.Map;public class HashMap1 {/*** 1. 两数之和* 给定一个整数数组nums和一个目标值target，找出数组中和为目标值的两个数的下标* * 算法思路：使用哈希表记录已遍历过的元素及其下标，实现O(n)时间复杂度的查找* 时间复杂度：O(n)，其中n是数组的长度，只需遍历一次数组* 空间复杂度：O(n)，最坏情况下需要存储n-1个元素到哈希表中* * @param nums   输入的整数数组* @param target 目标和值* @return 返回两个整数的下标，这两个整数的和等于目标值*/public static int[] twoSum(int[] nums, int target) {// 创建结果数组，用于存储找到的两个元素的下标int[] res = new int[2];// 处理边界情况：如果数组为空，直接返回空结果if(nums == null || nums.length == 0){return res;}// 创建哈希表，键为数组元素的值，值为元素在数组中的下标Map<Integer, Integer> map = new HashMap<>();// 遍历数组中的每个元素for(int i = 0; i < nums.length; i++){// 计算当前元素与目标值的差值int temp = target - nums[i];   // 这个差值就是我们需要在哈希表中查找的值// 检查哈希表中是否已经存在这个差值if(map.containsKey(temp)){// 如果存在，说明找到了和为target的两个元素res[1] = i;                // 当前元素的下标res[0] = map.get(temp);    // 之前元素的下标break;                     // 找到结果，退出循环}// 如果没找到匹配的差值，将当前元素及其下标加入哈希表map.put(nums[i], i);    // 键为元素值，值为下标}// 返回结果数组，包含两个元素的下标return res;}/*** 349. 两个数组的交集* 使用HashSet查找两个数组的交集元素* 时间复杂度O(n+m+k)，其中n是数组nums1的长度，m是数组nums2的长度，k是交集元素的个数* 空间复杂度O(n+k)，其中n是数组nums1的长度，k是交集元素的个数*/public static int[] findIntersection(int[] nums1, int[] nums2) {// 处理边界情况：如果任一数组为空，则交集为空if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {return new int[0];}// 创建一个HashSet存储nums1中的元素Set<Integer> set1 = new HashSet<>();// 创建一个HashSet存储交集结果Set<Integer> resSet = new HashSet<>();// 遍历数组1，将所有元素添加到set1中for (int i : nums1) {set1.add(i);}// 遍历数组2，如果元素在set1中存在，则添加到结果集合中for (int i : nums2) {if (set1.contains(i)) {resSet.add(i);}}// 将结果集合转换为数组int[] arr = new int[resSet.size()];int j = 0;for (int i : resSet) {arr[j++] = i;}return arr;}/*** 242. 有效的字母异位词 字典解法* 使用数组记录字符出现次数，比HashMap更高效* 时间复杂度O(m+n)，其中m和n分别是两个字符串的长度* 空间复杂度O(1)，因为使用固定大小的数组（26个字母）*/public static boolean isAnagram(String s, String t) {// 如果长度不同，必然不是字母异位词if (s.length() != t.length()) {return false;}// 创建大小为26的数组，对应26个小写字母int[] record = new int[26];// 遍历第一个字符串，统计每个字符出现的次数for (int i = 0; i < s.length(); i++) {// s.charAt(i) - 'a' 将字符转换为0-25的索引// 例如：'a'-'a'=0, 'b'-'a'=1, 'z'-'a'=25record[s.charAt(i) - 'a']++;}// 遍历第二个字符串，减去每个字符出现的次数for (int i = 0; i < t.length(); i++) {record[t.charAt(i) - 'a']--;}// 检查record数组中的所有元素是否都为0for (int count : record) {// 如果有元素不为0，说明字符出现次数不匹配// 即有些字符在一个字符串中出现次数多，在另一个字符串中出现次数少if (count != 0) {return false;}}// 所有元素都为0，说明两个字符串包含完全相同的字符集合// 即它们互为字母异位词return true;}/*** 202. 快乐数* 判断一个数是否为"快乐数"* 快乐数定义：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，* 然后重复这个过程直到这个数变为 1，或是无限循环但始终变不到 1。* 如果最终变为 1，那么这个数就是快乐数。* * 时间复杂度：O(log n)，因为对于一个数字n，计算其各位平方和的时间复杂度是O(log n)* 空间复杂度：O(log n)，需要用HashSet存储中间结果，最坏情况下可能需要存储O(log n)个数字*/public static boolean isHappy(int n) {// 使用HashSet记录已经出现过的数字，用于检测循环Set<Integer> record = new HashSet<>();// 当n不等于1且n没有在之前的计算中出现过时，继续计算while (n != 1 && !record.contains(n)) {// 将当前数字加入记录集合record.add(n);// 内联getNextNumber函数的逻辑：计算各位数字的平方和int res = 0;// 逐位取出数字并计算平方和while (n > 0) {// 取出最后一位数字int temp = n % 10;// 将该数字的平方加到结果中res += temp * temp;// 去掉最后一位数字n = n / 10;}n = res;}// 如果最终n等于1，则是快乐数；否则不是return n == 1;}/*** 计算一个数字的各位数字平方和* 例如：对于数字19，计算 1²+9² = 1+81 = 82* * @param n 输入的正整数* @return 各位数字的平方和*/private static int getNextNumber(int n) {int res = 0;// 逐位取出数字并计算平方和while (n > 0) {// 取出最后一位数字int temp = n % 10;// 将该数字的平方加到结果中res += temp * temp;// 去掉最后一位数字n = n / 10;}return res;}/*** 主函数，用于测试各种方法*/public static void main(String[] args) {// 测试findIntersection方法System.out.println("\n===== 测试数组交集函数 =====");// 测试用例1：有交集的两个数组int[] nums1 = {1, 2, 2, 1};int[] nums2 = {2, 2};System.out.println("测试用例1: " + Arrays.toString(nums1) + ", " + Arrays.toString(nums2));System.out.println("交集结果: " + Arrays.toString(findIntersection(nums1, nums2))); // 应输出[2]// 测试用例2：有多个交集元素的两个数组int[] nums3 = {4, 9, 5};int[] nums4 = {9, 4, 9, 8, 4};System.out.println("测试用例2: " + Arrays.toString(nums3) + ", " + Arrays.toString(nums4));System.out.println("交集结果: " + Arrays.toString(findIntersection(nums3, nums4))); // 应输出[4, 9]// 测试用例3：没有交集的两个数组int[] nums5 = {1, 2, 3};int[] nums6 = {4, 5, 6};System.out.println("测试用例3: " + Arrays.toString(nums5) + ", " + Arrays.toString(nums6));System.out.println("交集结果: " + Arrays.toString(findIntersection(nums5, nums6))); // 应输出[]// 测试isAnagram方法System.out.println("\n===== 测试字母异位词函数 =====");// 测试用例1：互为字母异位词的两个字符串String s1 = "anagram";String t1 = "nagaram";System.out.println("测试用例1: " + s1 + ", " + t1);System.out.println("结果: " + isAnagram(s1, t1)); // 应输出true// 测试用例2：不是字母异位词的两个字符串String s2 = "rat";String t2 = "car";System.out.println("测试用例2: " + s2 + ", " + t2);System.out.println("结果: " + isAnagram(s2, t2)); // 应输出false// 测试用例3：长度不同的两个字符串String s3 = "abcd";String t3 = "dcbaa";System.out.println("测试用例3: " + s3 + ", " + t3);System.out.println("结果: " + isAnagram(s3, t3)); // 应输出false// 测试isHappy方法System.out.println("\n===== 测试快乐数函数 =====");// 测试用例1：19是快乐数// 1² + 9² = 82// 8² + 2² = 68// 6² + 8² = 100// 1² + 0² + 0² = 1int num1 = 19;System.out.println("测试用例1: " + num1);System.out.println("结果: " + isHappy(num1)); // 应输出true// 测试用例2：2不是快乐数（会进入循环）// 2² = 4// 4² = 16// 1² + 6² = 37// 3² + 7² = 58// 5² + 8² = 89// 8² + 9² = 145// 1² + 4² + 5² = 42// 4² + 2² = 20// 2² + 0² = 4（此时进入循环）int num2 = 2;System.out.println("测试用例2: " + num2);System.out.println("结果: " + isHappy(num2)); // 应输出false// 测试用例3：7是快乐数int num3 = 7;System.out.println("测试用例3: " + num3);System.out.println("结果: " + isHappy(num3)); // 应输出true// 测试twoSum方法System.out.println("\n===== 测试两数之和函数 =====");// 测试用例1：标准情况int[] nums1 = {2, 7, 11, 15};int target1 = 9;System.out.println("测试用例1: 数组=" + Arrays.toString(nums1) + ", 目标值=" + target1);int[] result1 = twoSum(nums1, target1);System.out.println("结果: " + Arrays.toString(result1) + " (元素: " + nums1[result1[0]] + " + " + nums1[result1[1]] + " = " + target1 + ")");// 测试用例2：元素可以重复使用吗？不可以，因为下标不同int[] nums2 = {3, 2, 4};int target2 = 6;System.out.println("测试用例2: 数组=" + Arrays.toString(nums2) + ", 目标值=" + target2);int[] result2 = twoSum(nums2, target2);System.out.println("结果: " + Arrays.toString(result2) + " (元素: " + nums2[result2[0]] + " + " + nums2[result2[1]] + " = " + target2 + ")");// 测试用例3：只有一个解int[] nums3 = {3, 3};int target3 = 6;System.out.println("测试用例3: 数组=" + Arrays.toString(nums3) + ", 目标值=" + target3);int[] result3 = twoSum(nums3, target3);System.out.println("结果: " + Arrays.toString(result3) + " (元素: " + nums3[result3[0]] + " + " + nums3[result3[1]] + " = " + target3 + ")");}
}