【LeetCode刷题日记】：从 LeetCode 经典题看哈希表的场景化应用---数组、HashSet、HashMap 选型与算法实战

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺前言前面我们学习了哈希表的基础知识了解到了哈希表的多种实现方式最关键的问题就是如何选择的问题。哈希表一共有三种实现方式分别是数组HashSetHashMap这三种实现方式根据不同的情况选择不同的实现方式当然不用说但是在实际问题中我们如何快速高效的选择正确的实现方式是我们这篇文章要解决的问题结合具体的算法进行分析加深理解这里我们通过一题来引入数组实现和HashSet实现题目背景LeetCode349给定两个数组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 10000 nums1[i], nums2[i] 1000说明本题后面 力扣改了 题目描述 和 后台测试数据增添了 数值范围1 nums1.length, nums2.length 10000 nums1[i], nums2[i] 1000所以就可以 使用数组来做哈希表了 因为数组都是 1000以内的。那么接下来我们用两种实现方式来对比一下。方法一HashSet实现// 时间复杂度O(nmk) 空间复杂度O(nk) // 其中n是数组nums1的长度m是数组nums2的长度k是交集元素的个数 import java.util.HashSet; import java.util.Set; class Solution { public int[] intersection(int[] nums1, int[] nums2) { if (nums1 null || nums1.length 0 || nums2 null || nums2.length 0) { return new int[0]; } SetInteger set1 new HashSet(); SetInteger resSet new HashSet(); //遍历数组1 for (int i : nums1) { set1.add(i); } //遍历数组2的过程中判断哈希表中是否存在该元素 for (int i : nums2) { if (set1.contains(i)) { resSet.add(i); } } //方法1将结果集合转为数组 return res.stream().mapToInt(Integer::intValue).toArray(); /** * 将 SetInteger 转换为 int[] 数组 * 1. stream() : Collection 接口的方法将集合转换为 StreamInteger * 2. mapToInt(Integer::intValue) : * - 中间操作将 StreamInteger 转换为 IntStream * - 使用方法引用 Integer::intValue将 Integer 对象拆箱为 int 基本类型 * 3. toArray() : 终端操作将 IntStream 转换为 int[] 数组。 */ //方法2另外申请一个数组存放setRes中的元素,最后返回数组 int[] arr new int[resSet.size()]; int j 0; for(int i : resSet){ arr[j] i; } return arr; } }题目解析关于这道题我们先分析题目条件输出结果中的每个元素一定是唯一的也就是说输出的结果的去重的 同时可以不考虑输出结果的顺序而且当这道题目没有限制数值的大小就无法使用数组来做哈希表了。因为如果哈希值比较少、特别分散、跨度非常大使用数组就造成空间的极大浪费。那么我们为什么不能都是用set实现呢这里就要说明直接使用set 不仅占用空间比数组大而且速度要比数组慢set把数值映射到key上都要做hash计算的。不要小瞧 这个耗时在数据量大的情况差距是很明显的因此在写这道题的时候我们先创建两个HashSet用来存两个数组中的元素通过遍历把数组中的元素存入到Set中而在添加到set集合中的时候默认去重相同元素只能添加一次实现了题目中的输出的结果每个元素都是唯一的。但是如果不用 HashSet用普通 ArrayList 存就会变成 [2,2]不符合题意。然后后面我们将结果集合转换成数组即可。方法二数组实现class Solution { public int[] intersection(int[] nums1, int[] nums2) { int[] hash1 new int[1002]; int[] hash2 new int[1002]; for(int i : nums1) hash1[i]; for(int i : nums2) hash2[i]; ListInteger resList new ArrayList(); for(int i 0; i 1002; i) if(hash1[i] 0 hash2[i] 0) resList.add(i); int index 0; int res[] new int[resList.size()]; for(int i : resList) res[index] i; return res; } }题目解析具体实现思路和set集合实现方式是一样的这里去重的思路就是通过条件判断if(hash1[i] 0 hash2[i] 0)是否有重合的元素。根据题目的要求创建一个新的数组来接受结果并返回。接下来还是哈希表的HashSet实现这里没有说范围题目背景LeetCode202编写一个算法来判断一个数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 231 - 1题目答案class Solution { public boolean isHappy(int n) { SetInteger record new HashSet(); while (n ! 1 !record.contains(n)) { record.add(n); n getNextNumber(n); } return n 1; } private int getNextNumber(int n) { int res 0; while (n 0) { int temp n % 10; res temp * temp; n n / 10; } return res; } }题目解析首先根据题目的描述什么是快乐数我们通过定义一个方法来计算这个快乐数也就是写在下面的方法 getNextNumber返回这个结果然后在main方法里调用这个方法事先创建一个set集合关于while的循环条件只有当n不等于1并且集合里没有n时才进行循环因为n等于1时就已经是快乐数了不需要进行循环同时题目中还说了会出现无限循环的情况也就是说sum会重复因为我们通过判断是否存在过来避免重复。因为当n重复的时候直接不执行循环此时n也不可能等于1但返回是n1因此return false。接下来就是哈希表的Map实现题目背景LeetCode1给定一个整数数组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只会存在一个有效答案题目答案//使用哈希表 public int[] twoSum(int[] nums, int target) { int[] res new int[2]; if(nums null || nums.length 0){ return res; } MapInteger, Integer map new HashMap(); for(int i 0; i nums.length; i){ int temp target - nums[i]; // 遍历当前元素并在map中寻找是否有匹配的key if(map.containsKey(temp)){ res[1] i; res[0] map.get(temp); break; } map.put(nums[i], i); // 如果没找到匹配对就把访问过的元素和下标加入到map中 } return res; }题目解析首先强调一下什么时候使用哈希法当我们需要查询一个元素是否出现过或者一个元素是否在集合里的时候就要第一时间想到哈希法。本题呢我们就需要一个集合来存放我们遍历过的元素然后在遍历数组的时候去询问这个集合某元素是否遍历过也就是 是否出现在这个集合。那么我们就应该想到使用哈希法了。因为本题我们不仅要知道元素有没有遍历过还要知道这个元素对应的下标需要使用 key value结构来存放key来存元素value来存下标那么使用map正合适。再来看一下使用数组和set来做哈希法的局限。数组的大小是受限制的而且如果元素很少而哈希值太大会造成内存空间的浪费。set是一个集合里面放的元素只能是一个key而两数之和这道题目不仅要判断y是否存在而且还要记录y的下标位置因为要返回x 和 y的下标。所以set 也不能用。此时就要选择另一种数据结构map map是一种key value的存储结构可以用key保存数值用value再保存数值所在的下标。map目的用来存放我们访问过的元素因为遍历数组的时候需要记录我们之前遍历过哪些元素和对应的下标这样才能找到与当前元素相匹配的也就是相加等于target接下来是map中key和value分别表示什么。这道题 我们需要 给出一个元素判断这个元素是否出现过如果出现过返回这个元素的下标。那么判断元素是否出现这个元素就要作为key所以数组中的元素作为key有key对应的就是valuevalue用来存下标。所以 map中的存储结构为 {key数据元素value数组元素对应的下标}。在遍历数组的时候只需要向map去查询是否有和目前遍历元素匹配的数值如果有就找到的匹配对如果没有就把目前遍历的元素放进map中因为map存放的就是我们访问过的元素。总之res[0] map.get(temp); 把 “另一半数字” 的下标放进结果数组第一个位置res[1] i; 把 “当前数字” 的下标放进结果数组第二个位置两个下标合起来就是两数之和的答案。数组、Set、Map 核心对比表特点数组 (Array)SetMap存储结构有序、可重复、按下标访问无序、不重复、无下标存key-value 键值对查找速度遍历查找O (n)查找是否存在O (1)按 key 查 valueO (1)能否存重复值可以不可以key 不重复value 可以能否记下标本身自带下标不能记下标可以用 value 存下标典型用途存数据、遍历、排序去重、判断存在存映射关系数值→下标两数之和适用暴力法双层循环只能判断是否存在拿不到下标哈希法最优解能存值 下标想存值 下标→ 用Map想去重 / 判断存在→ 用Set想按顺序遍历→ 用数组结语如果对你有帮助请点赞关注收藏你的支持就是我最大的动力