【哈希系列】舍友担心期末考睡不着，我连夜准备了这套哈希全套专题

⭐️引言⭐️
大家好，我是执梗。今天为大家带来一套哈希套题的专项训练题型，哈希表在数据结构中占有非常重要的地位。很多同学总是学习了理论知识，缺乏实际使用。正所谓将军都是从战场上杀出来的，想要成为哈希大神，还得疯狂刷题。问题是很多同学他根本不知道如何找到合适的题目来训练，而且没有配套的答案解析。这里我为大家精心筛选了数道哈希经典例题，题目较为基础，能让初学者充分感受哈希的魅力，配上详细的代码思路解析，定让你收获满满。建议收藏，防止找不到，可以反复练习，题目总链接在末尾

📒博客首页：执梗的博客

🎉欢迎关注🔎点赞👍收藏⭐️留言📝

❤️ ：热爱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.哈希总结（题目总链接）

   哈希做法是经典的以空间换时间，我们做题一般都是更容易超时，哈希可以很好的帮我们解决这个问题。但是基础的题目只用哈希就可以，如果进阶的题目还需要和其他做法，比如双指针等等一起搭配。所以大家一定要打好哈希的基础，从简单题入手，不然以后用哈希都想不到。后续我也会写出哈希的进阶以及多种算法练习的练题集锦，希望大家收藏支持一下。

1.存在重复元素https://leetcode-cn.com/problems/contains-duplicate/2.存在重复元素||https://leetcode-cn.com/problems/contains-duplicate-ii/3.有效字母异位词https://leetcode-cn.com/problems/valid-anagram/4.两个数组的交集https://leetcode-cn.com/problems/intersection-of-two-arrays/5.快乐数https://leetcode-cn.com/problems/happy-number/6.赎金信https://leetcode-cn.com/problems/ransom-note/7.两数之和https://leetcode-cn.com/problems/two-sum/**加油！**
有帮助的老铁，还望给个三连，感谢！！！！！

文末小惊喜：

     ![](https://img-blog.csdnimg.cn/388d4b73fd934d358df8969311875e4e.png) 

Java学习路线总结，搬砖工逆袭Java架构师