??引言??
大家好，我是執梗，今天為大家帶來一套哈希套題的專項訓練題型，哈希表在資料結構中占有非常重要的地位，很多同學總是學習了理論知識，缺乏實際使用，正所謂將軍都是從戰場上殺出來的，想要成為哈希大神，還得瘋狂刷題，問題是很多同學他根本不知道如何找到合適的題目來訓練，而且沒有配套的答案決議，這里我為大家精心篩選了數道哈希經典例題，題目較為基礎，能讓初學者充分感受哈希的魅力，配上詳細的代碼思路決議，定讓你識訓滿滿，建議收藏，防止找不到，可以反復練習，題目總鏈接在末尾

📒博客首頁：執梗的博客

🎉歡迎關注🔎點贊👍收藏??留言📝

?? ：熱愛Java與演算法學習，期待一起交流！

🙏作者水平很有限，如果發現錯誤，求告知，多謝！

🌺有問題可私信交流！！！

??精彩回訪??

目錄

🍍1. 刷題與觀看須知

🍍2. 力克哈希，鏖戰力扣

🐄1.存在重復元素

🐏2.存在重復元素||

🐠3.有效的字母異位詞

🐟 4.兩個陣列的交集

🐳5.快樂數

🐋6.贖金信

🐬7.兩數之和

?? 3.哈希總結（題目總鏈接）

🍍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架構師