当前位置：首页 > news >正文

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

news 2026/6/6 1:19:24

🔥个人主页：北极的代码（欢迎来访）
🎬作者简介：java后端学习者
❄️个人专栏：苍穹外卖日记，SSM框架深入，JavaWeb
✨命运的结局尽可永在，不屈的挑战却不可须臾或缺！

前言：

前面我们学习了哈希表的基础知识，了解到了哈希表的多种实现方式，最关键的问题就是如何选择的问题。哈希表一共有三种实现方式，分别是数组，HashSet，HashMap，这三种实现方式，根据不同的情况选择不同的实现方式当然不用说，但是在实际问题中我们如何快速高效的选择正确的实现方式是我们这篇文章要解决的问题，结合具体的算法进行分析，加深理解！

这里我们通过一题来引入数组实现和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 <= 1000
0 <= nums1[i], nums2[i] <= 1000

说明：

本题后面力扣改了题目描述和后台测试数据，增添了数值范围：

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

所以就可以使用数组来做哈希表了，因为数组都是 1000以内的。那么接下来我们用两种实现方式来对比一下。

方法一：HashSet实现

// 时间复杂度O(n+m+k) 空间复杂度O(n+k) // 其中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]; } Set<Integer> set1 = new HashSet<>(); Set<Integer> 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(); /** * 将 Set<Integer> 转换为 int[] 数组： * 1. stream() : Collection 接口的方法，将集合转换为 Stream<Integer> * 2. mapToInt(Integer::intValue) : * - 中间操作，将 Stream<Integer> 转换为 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]++; List<Integer> 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) { Set<Integer> 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，但返回是n==1，因此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; } Map<Integer, 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对应的就是value，value用来存下标。
所以 map中的存储结构为 {key：数据元素，value：数组元素对应的下标}。
在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。
总之：
res[0] = map.get(temp);= 把 “另一半数字” 的下标放进结果数组第一个位置
res[1] = i;= 把 “当前数字” 的下标放进结果数组第二个位置
两个下标合起来，就是两数之和的答案。

数组、Set、Map 核心对比表

特点	数组 (Array)	Set	Map
存储结构	有序、可重复、按下标访问	无序、不重复、无下标	存key-value 键值对
查找速度	遍历查找：O (n)	查找是否存在：O (1)	按 key 查 value：O (1)
能否存重复值	可以	不可以	key 不重复，value 可以
能否记下标	本身自带下标	不能记下标	可以用 value 存下标
典型用途	存数据、遍历、排序	去重、判断存在	存映射关系（数值→下标）
两数之和适用	暴力法（双层循环）	只能判断是否存在，拿不到下标	哈希法最优解，能存值 + 下标