前言

在本篇文章中，我們重點講解哈希表在算法題目中的應用，不會涉及到太多哈希表的概念、原理等知識

首先，我們先來簡單回顧哈希表

哈希表知識回顧

哈希表是什么？

哈希表 是一種數(shù)據(jù)結(jié)構(gòu)，用于存儲鍵值對。通過將鍵轉(zhuǎn)換為索引來實現(xiàn)快速的數(shù)據(jù)訪問。具體而言，哈希表使用一個哈希函數(shù)將鍵映射到一個特定的索引，然后將值存儲在該索引位置上。這樣，在查找、插入或刪除元素時，可以通過哈希函數(shù)直接計算出元素應該存儲或者所在的位置，從而實現(xiàn)高效的數(shù)據(jù)操作。哈希表的查詢、插入和刪除操作的時間復雜度通常為O(1)。簡而言之，哈希表是存儲數(shù)據(jù)的容器，是一種非常高效的數(shù)據(jù)結(jié)構(gòu)

哈希表有什么作用？

 哈希表主要用于快速存儲、查找和刪除數(shù)據(jù)，在解決問題時，通常用于快速查找某個元素

什么時候使用哈希表？

（1）當我們需要 快速查找特定元素、 頻繁查找某一個元素 及 確定一個集合中是否存在重復元素 時，可以使用哈希表來存儲已經(jīng)訪問過的元素，從而實現(xiàn)快速查找和查重

（2）當需要統(tǒng)計數(shù)據(jù)中各個元素出現(xiàn)的次數(shù)，可以使用哈希表來存儲元素及其對應的計數(shù)值，快速實現(xiàn)統(tǒng)計和計數(shù)

（3）當需要建立兩個數(shù)據(jù)集之間的映射關系時，可以使用哈希表來實現(xiàn)映射

怎么使用哈希表？

（1）使用容器，在解決算法問題時，我們常使用的哈希表容器有兩種：HashMap 和 HashSet

（2）使用數(shù)組模擬簡易哈希表，例如，在數(shù)據(jù)范圍很小的時候，我們可以考慮使用int類型的數(shù)組來模擬哈希表

接下來，我們以一些練習來進一步掌握哈希表在算法題目中的應用

練習1：存在重復元素

題目鏈接：

217. 存在重復元素 - 力扣（LeetCode）

題目描述：

給你一個整數(shù)數(shù)組 nums 。如果任一值在數(shù)組中出現(xiàn) 至少兩次 ，返回 true ；如果數(shù)組中每個元素互不相同，返回 false 。

示例 1：

<strong>輸入：</strong>nums = [1,2,3,1]
<strong>輸出：</strong>true

示例 2：

<strong>輸入：</strong>nums = [1,2,3,4]
<strong>輸出：</strong>false

示例 3：

<strong>輸入：</strong>nums = [1,1,1,3,3,4,3,2,4,2]
<strong>輸出：</strong>true

提示：

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109

思路分析：

 首先我們來分析題目，在整數(shù)數(shù)組中，若有一個數(shù)在數(shù)組中出現(xiàn)了兩次以上，則返回true，否之，返回false。我們很容易想到暴力解法，即 固定一個元素，然后向后遍歷，觀察是否有與其相同的元素，其時間復雜度為 O(N ^ 2)，因此，當測試數(shù)據(jù)量較大時，會超出時間限制

在暴力枚舉時，由于我們每次固定一個元素再向后遍歷，因此，很多不符合的元素被重復遍歷，為了不遍歷這些不符合的元素，我們可以考慮使用哈希表來存放這些元素。對于數(shù)組中的每個元素，我們將其插入到哈希表中，若在插入前該元素已經(jīng)存在于哈希表中，則說明存在重復元素

代碼實現(xiàn)：

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> hash = new HashSet<>();
        for(int i = 0; i < nums.length; i++{
            if(hash.contains(nums[i])){
                return true;
            }else{
                hash.add(nums[i]);
            }
        }
        return false;
    }
}

練習2：存在重復元素II

題目鏈接：

219. 存在重復元素 II - 力扣（LeetCode）

題目描述：

給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k ，判斷數(shù)組中是否存在兩個 不同的索引 i 和 j ，滿足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否則，返回 false 。

示例 1：

<strong>輸入：</strong>nums = [1,2,3,1], k = 3
<strong>輸出：</strong>true

示例 2：

<strong>輸入：</strong>nums = [1,0,1,1], k = 1
<strong>輸出：</strong>true

示例 3：

<strong>輸入：</strong>nums = [1,2,3,1,2,3], k = 2
<strong>輸出：</strong>false

提示：

• 1 <= nums.length <= 105
• -109 <= nums[i] <= 109
• 0 <= k <= 105

思路分析：

 本題的解題思路與練習1類似，但不同的是：在找到兩個相同元素時，要判定這兩個元素的下標絕對值是否小于等于k。因此，我們既要保存數(shù)組元素，還要保存元素下標。

由于數(shù)組中同一個元素可能出現(xiàn)兩次以上，當判斷兩個相同元素的數(shù)組下標的差（abs(i - j)）大于k時，要將哈希表中的下標更新為當前下標。例如：

代碼實現(xiàn)：

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Map<Integer, Integer> hash = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(hash.containsKey(nums[i]) && (i - hash.get(nums[i]) <= k)){
                return true;
            }else{
                hash.put(nums[i], i);
            }
        }
        return false;
    }
}

練習3：兩數(shù)之和

題目鏈接：

1. 兩數(shù)之和 - 力扣（LeetCode）

題目描述：

給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標值 target，請你在該數(shù)組中找出 和為目標值 target  的那 兩個 整數(shù)，并返回它們的數(shù)組下標。

你可以假設每種輸入只會對應一個答案。但是，數(shù)組中同一個元素在答案里不能重復出現(xiàn)。

你可以按任意順序返回答案。

示例 1：

<strong>輸入：</strong>nums = [2,7,11,15], target = 9
<strong>輸出：</strong>[0,1]
<strong>解釋：</strong>因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

<strong>輸入：</strong>nums = [3,2,4], target = 6
<strong>輸出：</strong>[1,2]

示例 3：

<strong>輸入：</strong>nums = [3,3], target = 6
<strong>輸出：</strong>[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只會存在一個有效答案

思路分析：

本題要求我們在整數(shù)數(shù)組中找到兩個元素，這兩個元素的和為target，本題與練習1的解題思路類似，我們可以使用哈希表來存放整數(shù)數(shù)組中的元素及其下標，在哈希表中尋找是否存在元素 target - nums[i]，需要注意的是，若我們先將數(shù)組中所有元素和下標都存放在哈希表中，然后再遍歷數(shù)組，查找哈希表中是否存在元素 target - nums[i]，此時可能會出現(xiàn)同一個元素在答案中重復出現(xiàn)的情況（例如：target = 8，nums = [1, 2, 4, 3]，當前元素nums[2] = 4，由于數(shù)組中所有元素及下標已經(jīng)放在哈希表中，因此此時元素4存在于哈希表中，但其下標與當前下標相同，即一個元素在答案中重復出現(xiàn)）

因此，若我們先將數(shù)組中所有元素和下標放入哈希表時，在查找哈希表中是否存在元素 target - nums[i]時，還需要判斷其下標是否與當前下標相同

我們還可以邊遍歷數(shù)組，邊向數(shù)組中存放元素，此時，哈希表中存放的元素為 nums[i]之前的元素，查找當前元素之前是否存在元素 = target - nums[i]，這樣，就不需要對下標進行判斷了

代碼實現(xiàn)：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for(int i = 1; i < nums.length; i++){
            for(int j = i - 1; j >= 0; j--){
                if(nums[i] + nums[j] == target){
                    return new int[] {i, j};
                }
            }
        }
        return null;
    }
}

練習4：判定是否互為字符重排

題目鏈接：

面試題 01.02. 判定是否互為字符重排 - 力扣（LeetCode）

題目描述：

給定兩個由小寫字母組成的字符串 s1 和 s2，請編寫一個程序，確定其中一個字符串的字符重新排列后，能否變成另一個字符串。

示例 1：

<strong>輸入:</strong> <code>s1</code> = "abc", <code>s2</code> = "bca"
<strong>輸出:</strong> true

示例 2：

<strong>輸入:</strong> <code>s1</code> = "abc", <code>s2</code> = "bad"
<strong>輸出:</strong> false

說明：

• 0 <= len(s1) <= 100
• 0 <= len(s2) <= 100

思路分析：

題目要求我們判斷字符串s1和s2是否 是s1中的字符重新排列后，變?yōu)閟2。若s1中的字符能夠重新排列成s2，則s1中的字符與s2中的字符相同。要想保證兩字符串字符相同，首先兩字符串的長度必須相同，因此，我們先判斷兩字符串長度是否相同，若相同，我們再來判斷其中字符是否都相同。

我們可以使用哈希表來保存字符及其出現(xiàn)的次數(shù)，先遍歷s1，保存其所有的字符及其出現(xiàn)的次數(shù)，再遍歷s2，若當前字符不在哈希表中，則兩字符串中存在不相同的字符，直接返回false；若當前字符在哈希表中，則次數(shù) - 1，若次數(shù) - 1 之后為 -1，則說明當前字符出現(xiàn)次數(shù)大于 s1中出現(xiàn)次數(shù)，兩字符串字符不完全相同，返回false。若完成遍歷，則說明兩字符串中的字符完全相同，返回true

由于兩個字符串中的字符都是由小寫字母構(gòu)成的，因此，我們可以使用數(shù)組來模擬哈希表，創(chuàng)建一個大小為26的int類型數(shù)組，下標表示字符（例如 a 對應下標 0，b對應下標 1...）而元素表示字符的出現(xiàn)次數(shù)

代碼實現(xiàn)：

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if(s1.length() != s2.length()) return false;//先判斷長度是否相同
        if(s1 == null) return true;//若兩字符串都為空，則直接返回true
        int[] hash = new int[26];//使用int數(shù)組模擬哈希表
        for(int i = 0; i < s1.length(); i++){//先遍歷s1，將字符及其出現(xiàn)次數(shù)存放在哈希表中
            hash[s1.charAt(i) - 'a']++;
        }
        for(int i = 0; i < s2.length(); i++){//再遍歷s2，判斷兩字符是否相同
           if(--hash[s2.charAt(i) - 'a'] < 0) return false; 
        }
        return true;
    }
}

練習5：字母異位詞分組

題目鏈接：

49. 字母異位詞分組 - 力扣（LeetCode）

題目描述：

給你一個字符串數(shù)組，請你將 字母異位詞 組合在一起。可以按任意順序返回結(jié)果列表。

字母異位詞 是由重新排列源單詞的所有字母得到的一個新單詞。

示例 1:

<strong>輸入:</strong> strs = <code>["eat", "tea", "tan", "ate", "nat", "bat"]</code>
<strong>輸出: </strong>[["bat"],["nat","tan"],["ate","eat","tea"]]

示例 2:

<strong>輸入:</strong> strs = <code>[""]</code>
<strong>輸出: </strong>[[""]]

示例 3:

<strong>輸入:</strong> strs = <code>["a"]</code>
<strong>輸出: </strong>[["a"]]

提示：

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] 僅包含小寫字母

思路分析：

字母異位詞與 練習4 中的 字符重排 相同，即 兩個字符串中的所有字符相同。題目要求我們將所有 字母異位詞組合在一起，即將 所有字符相同的字符串放在一個集合中

首先，我們解決第一個問題：如何判斷字母異位詞？

在 練習4 中，我們使用數(shù)組模擬的哈希表來判斷兩個字符串是否互為字符重排，但在本題中，我們不能繼續(xù)使用這種方式來判斷字母異位詞，因為本題中存在許多組字母異位詞，若通過這種方式來判斷字母異位詞，則每次都需要遍歷不同組字母異位詞和當前字符串。在這里，我們可以考慮將字符串按照 ASCII碼值進行升序排列，（例如：eat 排列后 為 aet，tea排列后 為 aet）此時，只需要判斷排列后的字符串是否相同，即可判斷出兩個字符串是否為同一組字母異位詞

接下來，我們解決第二個問題：如何將字母異位詞組合在一起？

 哈希表可以統(tǒng)計數(shù)據(jù)中各個元素出現(xiàn)的次數(shù)，使用哈希表可以存儲元素及其對應的計數(shù)值，在這里，我們可以使用哈希表 存儲 排列后的字符串 及其 字母異位詞，即 key：存儲排列后的字符串，value：存儲 List，其中存放的元素類型為 String，這樣，就可以將字母異位詞存放在List中 

因此，我們只需要遍歷字符串數(shù)組，將其按照ASCII碼值進行升序排列，然后判斷排列后的字符串是否已經(jīng)存在于哈希表中，若存在，則將 字母異位詞 放入List中；若不存在，則創(chuàng)建新的ArrayList

代碼實現(xiàn)：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();
        for(String str: strs){
            char[] chs = str.toCharArray();
            Arrays.sort(chs);
            String key = new String(chs);
            List list = hash.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            hash.put(key, list);
        }
        return new ArrayList<List<String>>(hash.values());
    }
}

總結(jié) 

到此這篇關于哈希表在算法題目中的實際應用的文章就介紹到這了,更多相關Java算法題中哈希表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論