前言

在本篇文章中，我們重點(diǎn)講解哈希表在算法題目中的應(yīng)用，不會(huì)涉及到太多哈希表的概念、原理等知識(shí)

首先，我們先來(lái)簡(jiǎn)單回顧哈希表

哈希表知識(shí)回顧

哈希表是什么？

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

哈希表有什么作用？

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

什么時(shí)候使用哈希表？

（1）當(dāng)我們需要 快速查找特定元素、 頻繁查找某一個(gè)元素 及 確定一個(gè)集合中是否存在重復(fù)元素 時(shí)，可以使用哈希表來(lái)存儲(chǔ)已經(jīng)訪問(wèn)過(guò)的元素，從而實(shí)現(xiàn)快速查找和查重

（2）當(dāng)需要統(tǒng)計(jì)數(shù)據(jù)中各個(gè)元素出現(xiàn)的次數(shù)，可以使用哈希表來(lái)存儲(chǔ)元素及其對(duì)應(yīng)的計(jì)數(shù)值，快速實(shí)現(xiàn)統(tǒng)計(jì)和計(jì)數(shù)

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

怎么使用哈希表？

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

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

接下來(lái)，我們以一些練習(xí)來(lái)進(jìn)一步掌握哈希表在算法題目中的應(yīng)用

練習(xí)1：存在重復(fù)元素

題目鏈接：

217. 存在重復(fù)元素 - 力扣（LeetCode）

題目描述：

給你一個(gè)整數(shù)數(shù)組 nums 。如果任一值在數(shù)組中出現(xiàn) 至少兩次 ，返回 true ；如果數(shù)組中每個(gè)元素互不相同，返回 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

思路分析：

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

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

代碼實(shí)現(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;
    }
}

練習(xí)2：存在重復(fù)元素II

題目鏈接：

219. 存在重復(fù)元素 II - 力扣（LeetCode）

題目描述：

給你一個(gè)整數(shù)數(shù)組 nums 和一個(gè)整數(shù) k ，判斷數(shù)組中是否存在兩個(gè) 不同的索引 i 和 j ，滿(mǎn)足 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

思路分析：

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

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

代碼實(shí)現(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;
    }
}

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

題目鏈接：

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

題目描述：

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

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

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

示例 1：

<strong>輸入：</strong>nums = [2,7,11,15], target = 9
<strong>輸出：</strong>[0,1]
<strong>解釋?zhuān)?lt;/strong>因?yàn)?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
• 只會(huì)存在一個(gè)有效答案

思路分析：

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

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

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

代碼實(shí)現(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;
    }
}

練習(xí)4：判定是否互為字符重排

題目鏈接：

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

題目描述：

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

示例 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

說(shuō)明：

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

思路分析：

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

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

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

代碼實(shí)現(xiàn)：

class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if(s1.length() != s2.length()) return false;//先判斷長(zhǎng)度是否相同
        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;
    }
}

練習(xí)5：字母異位詞分組

題目鏈接：

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

題目描述：

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

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

示例 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] 僅包含小寫(xiě)字母

思路分析：

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

首先，我們解決第一個(gè)問(wèn)題：如何判斷字母異位詞？

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

接下來(lái)，我們解決第二個(gè)問(wèn)題：如何將字母異位詞組合在一起？

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

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

代碼實(shí)現(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é) 

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

最新評(píng)論