⭐️引言⭐️
大家好，我是执梗。今天为大家带来一套哈希套题的专项训练题型，哈希表在数据结构中占有非常重要的地位。很多同学总是学习了理论知识，缺乏实际使用。正所谓将军都是从战场上杀出来的，想要成为哈希大神，还得疯狂刷题。问题是很多同学他根本不知道如何找到合适的题目来训练，而且没有配套的答案解析。这里我为大家精心筛选了数道哈希经典例题，题目较为基础，能让初学者充分感受哈希的魅力，配上详细的代码思路解析，定让你收获满满。建议收藏，防止找不到，可以反复练习，题目总链接在末尾
📒博客首页：执梗的博客
🎉欢迎关注🔎点赞👍收藏⭐️留言📝
❤️ ：热爱Java与算法学习，期待一起交流！
🙏作者水平很有限，如果发现错误，求告知，多谢！
🌺有问题可私信交流！！！
⭐️精彩回访⭐️
【几数之和系列】几数之和套题专项训练回放链接【链表套题系列】刷完这套链表专题，吓倒面试官回放链接
🍍1. 刷题与观看须知
任何算法题目，你光看不自己去实现，都不算真正地学到了自己的知识库中。所以推荐兄弟们有空要通过题目链接**一定要去自己尝试写**。而且即使做出来了，也要去想办法优化自己的代码，即使是同样的方法，也许别人写的更加简洁易懂。也要去学习复杂度更低更优秀的解题方法，正所谓条条大路通罗马，我走了较远的那条路，但我们到了终点也该学习一下更短的路，不然下次仍然会走最远的路，这就脱离了学习的本质了。
🍍2. 力克哈希，鏖战力扣
🐄1.存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果存在一值在数组中出现至少两次，函数返回
true。如果数组中每个元素都不相同，则返回
false。
题目链接：存在重复元素
题目分析：这个题目的名称，就已经是用哈希的标志了，拿这道题作为哈希的入门实在是最好不过了，**哈希经典的以空间换时间（升高空间复杂度降低时间复杂度）**。我也贴上排序做法的代码供大家对比。
**方法1：排序**
时间复杂度O(nlongn)：主要是排序的开销，如果是朴素的两层for循环暴力遍历开销为O(n^2)
空间复杂度O(nlogn)：排序的开销
class Solution {
public boolean containsDuplicate(int[] nums) {
//排序
Arrays.sort(nums);
int n=nums.length;
//看相邻的是否相等
for(int i=0;i<n-1;i++){
if(nums[i]==nums[i+1]){
return true;
}
}
return false;
}
}
**方法2：哈希判重**
** **复杂度O(n):n为nums的长度，主要是循环的耗时
复杂度O(n):n为nums的长度，主要是哈希的开销，最差的情况下数组全部都被放入set中
class Solution {
public boolean containsDuplicate(int[] nums) {
Set<Integer> set=new HashSet<Integer>();
int n=nums.length;
for(int i=0;i<n;i++){
if(!set.contains(nums[i])){
set.add(nums[i]);
}else{
return true;
}
}
return false;
}
}
🐏2.存在重复元素||
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 **nums [i] = nums [j]**，并且 i 和 j 的差的 绝对值 至多为 k。
题目链接：存在重复元素||
题目分析：这道题是第一题的进阶，在第一题的要求上做了一定的要求，更加适合哈希的做法，因为涉及到索引，我们需要把set转换成map，key保存值，value保存下标索引。
**方法1：哈希判重**
** **时间复杂度O(n)：n为nums的长度，主要是循环的耗时，最差情况整个数组遍历完。
空间复杂度O(n)：n为nums的长度，主要为哈希的开销
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
//key存值,value存下标
Map<Integer,Integer> map=new HashMap<>();
int n=nums.length;
for(int i=0;i<n;i++){
//没有这个数，存入map中
if(!map.containsKey(nums[i])){
map.put(nums[i],i);
}else{
//不满足题目的要求
if(map.get(nums[i])-i>k||i-map.get(nums[i])>k){
//更新下标,防止这个数后面再出现就满足要求了
map.put(nums[i],i);
}else{
//满足要求返回true
return true;
}
}
}
//结束完说明没有返回false
return false;
}
}
🐠3.有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
题目链接：有效的字母异位词
题目解析：这道题目的意思很简单，就是字符串出现的字母和频率都相同即可，这是非常经典的使用哈希的特征。但这里我想让大家知道，排序才是最简单的方法，也是大家都应该想到的。不仅是数字可以排序，字母也是可以排序的，如果是有效的字母异位词，排序后的char[]肯定一模一样。但是大家一定要知道。既然是哈希专场，利用哈希大家也一定要会做。
** 方法1：转换为char[]排序后进行对比**。
时间复杂度O(nlogn)：排序的时间是O(nlogn)，遍历的世界是O(n)，加起来还是算O(nlogn)
空间复杂度:O(logn)。排序API需要O(logn)的复杂度，而且如果是Java语言的话，由于String的不可变性，还得再用O(n)的空间来拷贝数组。
class Solution {
public boolean isAnagram(String s, String t) {
//先将字符串都转换为字符数组
char[] arr1=s.toCharArray();
char[] arr2=t.toCharArray();
//sort函数也可以传入字符数组
Arrays.sort(arr1);
Arrays.sort(arr2);
//Arrays有一个重写的equals方法
//可以直接比较两个数组是否完全一样
return Arrays.equals(arr2,arr1);
}
}
**方法2：利用数组来映射哈希。**我们要知道数组也是哈希的提现，索引下标相当于key，存储的值相当于value。我们可以用一个长度为26的char数组来存在从a到z每个数字出现的频率，在遍历s时遇到的每个字符出现的次数+1，遍历t时减1。如果最后数组中不全为0则说明不是有效的字母异位词。
时间复杂度O(n)：n为较长一条字符串的长度，主要是遍历
空间复杂度O(1)：常数级的数组消耗也只算O(1)
class Solution {
public boolean isAnagram(String s, String t) {
//从下标0存储a开始来存储每个数字出现的频率
int[] arr=new int[26];
//遍历字符串s
for(int i=0;i<s.length();i++){
//s.charAt(i)-'a'是为了找到每个字符对应的索引下标
arr[s.charAt(i)-'a']++;
}
for(int i=0;i<t.length();i++){
arr[t.charAt(i)-'a']--;
}
//遍历到不为0的说明有字母数量不相等，返回false
for(int i=0;i<arr.length;i++){
if(arr[i]!=0) return false;
}
//遍历结束没返回false说明是有效的字母异位，返回true
return true;
}
}
🐟 4.两个数组的交集
给定两个数组，编写一个函数来计算它们的交集。（好像还没见过那么短的题目）
题目链接：两个数组的交集
题目分析：比较直接的方法是遍历nums1，对于它的每一个元素，在遍历nums2的时候判断该元素是否在数组nums2中。这里我们才用两个Set集合，哈希查询元素的效率是O(1)，可以帮助我们降低时间复杂度。
** 方法1：利用HashSet**
时间复杂度O(n):n为nums1和num2的长度更长的那个，主要是用与两数组的遍历。
空间复杂度O(n)：n是num1的长度，最坏的情况下整个nums1都被装入到set中。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int n1=nums1.length;
int n2=nums2.length;
//用来存放其中一个数组
Set set=new HashSet();
//答案的长度不会超过短数组的长度
int[] arr=new int[Math.min(n1,n2)];
for(int i=0;i<n1;i++){
//set是不允许存放重复元素的，不用担心是否重复存入
set.add(nums1[i]);
}
//用来作为给答案数组放答案的指针
int j=0;
for(int i=0;i<n2;i++){
//判断set中是否有，如果有说明两个数组都有
if(set.contains(nums2[i])){
//加入答案数组
arr[j++]=nums2[i];
//加入后就从set中去掉，防止nums2有重复的再次加入
set.remove(nums2[i]);
}
}
//答案数组没有装满，就将后面减掉
return Arrays.copyOf(arr,j);
}
}
** 方法2：排序加双指针**
为了获得数组的交集，我们可以将数组排序，然后利用两个指针分别指向两个数组的起始端，然后判断。如果相等，则加入进答案数组，在加入前需要判断是否已经加入过，然后两指针向右移动一位。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1==null||nums1.length==0||nums2==null||nums2.length==0){
return new int[0];
}
//排序数组
Arrays.sort(nums1);
Arrays.sort(nums2);
int[] arr=new int[Math.min(nums1.length,nums2.length)];
//双指针
int p1=0;
int p2=0;
//用来放入答案数组的指针
int index=0;
while(p1<nums1.length&&p2<nums2.length){
if(nums1[p1]==nums2[p2]){
//确保答案不重复
if(index==0||nums1[p1]!=arr[index-1]){
arr[index++]=nums1[p1];
}
//无论是否放入数组，都应该++
p1++;
p2++;
}else if(nums1[p1]>nums2[p2]){
p2++;
}else{
p1++;
}
}
return Arrays.copyOfRange(arr,0,index);
}
}
🐳5.快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 true ；不是，则返回 false 。题目链接：快乐数
题目分析：我们可以猜想，如果一个数字如果不是快乐数，那它在进行题目要求的操作时一定会有循环，也就是会产生重复数字。这是一个猜想，但也确实如此，它的证明是需要数学来证明的，但是这个猜想其实也很容易想到。一直循环下去肯定会出现重复数字导致循环。这样我们就可以利用HashSet来判断重复。
**方法1：哈希检测循环**
时间复杂度O(logn)：这道题目时间复杂度不好分析，因为我们不知道循环会多少次，无法去准备计算，大家了解是O(logn)即可
空间复杂度O(logn)：同理于上
class Solution {
public boolean isHappy(int n) {
//用来存储每次操作以后的数
Set<Integer> set=new HashSet<>();
//先将n放入
set.add(n);
//一直循环，哈希检测
while(true){
//x保存n操作以后的值
int x=test(n);
//说明是快乐数
if(x==1){
return true;
}
//未出现的数，放入set
if(!set.contains(x)){
set.add(x);
//出现过的数，说明不是快乐数
}else{
return false;
}
//把x赋值回给n
n=x;
}
}
//写一个操作方法
public int test(int n){
int count=0;
while(n!=0){
int a=n%10;
count+=a*a;
n=n/10;
}
return count;
}
}
🐋6.赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
题目链接：赎金信
题目解析：这道题目和前面第一道题的做法基本一模一样，只不过要求有一点点变化，这里直接贴上代码，只在第一题上稍微改动一下即可
**方法：数组哈希映射**
** **时间复杂度O(n)：n为ransomNote和magazine更长的字符串的长度。主要是遍历的耗时
空间复杂度O(1)：常数级数组的消耗视为O(1)
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] arr=new int[26];
for(int i=0;i<ransomNote.length();i++){
arr[ransomNote.charAt(i)-'a']--;
}
for(int i=0;i<magazine.length();i++){
arr[magazine.charAt(i)-'a']++;
}
for(int i=0;i<26;i++){
if(arr[i]<0){
//小于0说明不够
return false;
}
}
return true;
}
}
🐬7.两数之和
给定一个整数数组
nums和一个整数目标值
target，请你在该数组中找出 **和为目标值 ***
target
- 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
题目链接：两数之和
题目分析：不能太经典的题目，我在几数之和系列中也详细讲解过，这里就只为大家贴上哈希的做法。
时间复杂度O(n)：n为nums的长度，主要是循环的耗时
空间复杂度O(n)：n为nums的长度，主要是哈希的开销
class Solution {
public int[] twoSum(int[] nums, int target) {
int n=nums.length;
//key存放值，value存放下标
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<n;i++){
//找到了
if(map.containsKey(target-nums[i])){
//返回下标
return new int[]{map.get(target-nums[i]),i};
}
//没找到放入map中
map.put(nums[i],i);
}
//遍历结束仍然未找到
return new int[0];
}
}
☀️ 3.哈希总结（题目总链接）
哈希做法是经典的以空间换时间，我们做题一般都是更容易超时，哈希可以很好的帮我们解决这个问题。但是基础的题目只用哈希就可以，如果进阶的题目还需要和其他做法，比如双指针等等一起搭配。所以大家一定要打好哈希的基础，从简单题入手，不然以后用哈希都想不到。后续我也会写出哈希的进阶以及多种算法练习的练题集锦，希望大家收藏支持一下。
文末小惊喜：
Java学习路线总结，搬砖工逆袭Java架构师
本文转载自: https://blog.csdn.net/m0_57487901/article/details/122224136
版权归原作者 Java执梗 所有， 如有侵权，请联系我们删除。
版权归原作者 Java执梗 所有， 如有侵权，请联系我们删除。