目錄

前言

一、什么是哈希表

二、哈希表的操作

2.1 操作時(shí)間復(fù)雜度

2.2 哈希表通用API

2.3 建立哈希表

2.3 哈希表常見(jiàn)結(jié)構(gòu)介紹

Set（集合）

Map（映射）

unordered_map（哈希表）

三、哈希表的力扣經(jīng)典題目

有效的字母異位詞242

兩個(gè)數(shù)組的交集 349

兩數(shù)之和1

四數(shù)相加II 454

三數(shù)之和 15

四數(shù)之和 18

前言

本文將從哈希表的概念、復(fù)雜度、STL實(shí)現(xiàn)函數(shù)、哈希表相關(guān)經(jīng)典題目展開(kāi)敘述。

一、什么是哈希表

哈希表是散列表，就是通過(guò)關(guān)鍵碼值而直接進(jìn)行訪問(wèn)的一種數(shù)據(jù)結(jié)構(gòu)

哈希表中關(guān)鍵碼就是數(shù)組的索引下標(biāo)，然后通過(guò)下標(biāo)直接訪問(wèn)數(shù)組中的元素

其內(nèi)部由一個(gè)個(gè)key：value 樣式的鍵值對(duì)組成。

哈希表中的key通過(guò)哈希函數(shù)得到內(nèi)存地址，然后將key和value放到對(duì)應(yīng)的內(nèi)存地址，從而實(shí)現(xiàn)通過(guò)key獲取Value的方式

哈希碰撞：2個(gè)不同的key通過(guò)哈希函數(shù)（hash function）得到了相同的內(nèi)存地址，也就是是內(nèi)存地址已經(jīng)被一個(gè)占用了，解決方法是將其中之一變?yōu)殒湵斫Y(jié)構(gòu)，使用next指向。這樣內(nèi)存地址就不會(huì)重復(fù)，但是會(huì)影響查詢

二、哈希表的操作

2.1 操作時(shí)間復(fù)雜度

1) 搜索：1.無(wú)哈希碰撞，直接用哈希函數(shù)通過(guò)Key定位到內(nèi)存地址,復(fù)雜度O(1)? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?2.有哈希碰撞，因?yàn)榇嬖趦?nèi)存地址需要通過(guò)鏈表查詢,復(fù)雜度O(N)

2)?插入：通過(guò)key找到內(nèi)存地址插入即可,復(fù)雜度 O(1)--自動(dòng)插入

unorder_map<int,int> InquireMap;
InquireMap[val] = 1;

3) 刪除：通過(guò)key找到內(nèi)存地址刪除即可,復(fù)雜度 O(1)

2.2 哈希表通用API

• begin()：該函數(shù)返回一個(gè)指向哈希表開(kāi)始位置的迭代器
• end()：返回一個(gè)指向哈希表結(jié)尾位置的下一個(gè)元素的迭代器
• empty()：判斷哈希表是否為空，空則返回true，非空返回false
• size()：返回哈希表的大小
• erase()： 刪除某個(gè)位置的元素，或者刪除某個(gè)位置開(kāi)始到某個(gè)位置結(jié)束這一范圍內(nèi)的元素， 或者傳入key值刪除鍵值對(duì)
• at()：根據(jù)key查找哈希表中的元素
• clear()：清空哈希表中的元素
• find()：以key作為參數(shù)尋找哈希表中的元素，如果哈希表中存在該key值則返回該位置上的迭代器，否則返回哈希表最后一個(gè)元素下一位置上的迭代器
• count()： 統(tǒng)計(jì)某個(gè)key值對(duì)應(yīng)的元素個(gè)數(shù) （注：因?yàn)閡nordered_map不允許重復(fù)元素，所以返回值為0或1）

2.3 建立哈希表

unordered_map<char,int> correspond{
        {'I',1},
        {'V',5},
        {'X',10},
        {'L',50},
        {'C',100},
        {'D',500},
        {'M',1000},
    };

2.3 哈希表常見(jiàn)結(jié)構(gòu)介紹

總體結(jié)構(gòu)上分為數(shù)組、set、map

數(shù)組也是一種意義上的哈希表

set的結(jié)構(gòu)中每個(gè)元素都是一個(gè)值（類似于數(shù)組）

map的結(jié)構(gòu)是一個(gè) key:value 的數(shù)據(jù)結(jié)構(gòu)

Set（集合）

1） set、multiset 基于紅黑樹(shù)（一種平衡二叉搜索樹(shù)），所以（key）值都是有序的，但是不可以修改，一旦修改就會(huì)引起整棵樹(shù)的錯(cuò)亂，所以只能刪除和增加，兩者唯一的區(qū)別是前者不可重復(fù)（key）值，后者可以重復(fù)

2）unordered_set?底層實(shí)現(xiàn)為哈希表，區(qū)別就是沒(méi)有關(guān)鍵碼這個(gè)說(shuō)法,哈希表是無(wú)序的，所以查詢效率要快些O(1)就可以實(shí)現(xiàn)。因?yàn)闊o(wú)序，所以值也不可以重復(fù)

小結(jié)：當(dāng)我們要使用集合來(lái)解決哈希問(wèn)題的時(shí)候，優(yōu)先使用unordered_set，因?yàn)樗牟樵兒驮鰟h效率是最優(yōu)的，如果需要集合是有序的，那么就用set，如果要求不僅有序還要有重復(fù)數(shù)據(jù)的話，那么就用multiset。

這三種數(shù)據(jù)結(jié)構(gòu)的具體優(yōu)劣在這里引用一張表來(lái)直觀體現(xiàn)

Map（映射）

1）map、multimap? 基于紅黑樹(shù)（一種平衡二叉搜索樹(shù)），key是有序的，和上面提到的set、multimap一樣，key值可以添加、刪除，但是不可以更改（map中，對(duì)key是有限制，對(duì)value沒(méi)有限制的。所以說(shuō)value值可以修改）兩者唯一的區(qū)別是前者不可重復(fù)key值，后者可以重復(fù)

2）unordered_map?底層實(shí)現(xiàn)為哈希表（無(wú)序），因?yàn)闊o(wú)序，所以key也不可以重復(fù)

unordered_map（哈希表）

這個(gè)數(shù)據(jù)結(jié)構(gòu)更加常用，所以在這里特別講一下它的性質(zhì)

• unordered_map底層存儲(chǔ)的是<key,value>鍵值對(duì)，可以通過(guò)key快速的索引到value unordered_map內(nèi)部因?yàn)槭菙?shù)據(jù)是通過(guò)映射存入哈希桶內(nèi)的，所以對(duì)unordered_map進(jìn)行遍歷得到的是一個(gè)無(wú)序的序列。
• unordered_map通過(guò)key進(jìn)行訪問(wèn)的速度比map快，但是遍歷元素的迭代效率就要低于map了。unordered_map也實(shí)現(xiàn)了operator[ ] 可以通過(guò)key直接訪問(wèn)到value

三、哈希表的力扣經(jīng)典題目

有效的字母異位詞242

給定兩個(gè)字符串 s 和 t ，編寫(xiě)一個(gè)函數(shù)來(lái)判斷 t 是否是 s 的字母異位詞。

注意：若?s 和 t?中每個(gè)字符出現(xiàn)的次數(shù)都相同，則稱?s 和 t?互為字母異位詞。

示例?1:

輸入: s = "anagram", t = "nagaram"
輸出: true

class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash[26] = {0};//26個(gè)英文字符
        for(int i =0 ;i<s.size();i++){
            hash[s[i]-'a']++;
        }

        for(int i =0 ;i<t.size();i++){
            hash[t[i]-'a']--;
        }

        for(int i =0 ;i<26;i++){
            if(hash[i] != 0){
                return false;
            }
        }
        return true;
    }
};

題解:

使用哈希表的一種實(shí)現(xiàn)方式--數(shù)組--通過(guò)索引存儲(chǔ)對(duì)應(yīng)的值。

具體體現(xiàn)于每一個(gè)元素與‘a(chǎn)’的差值作為索引，出現(xiàn)次數(shù)作為索引對(duì)應(yīng)的值，通過(guò)判斷出現(xiàn)次數(shù)是否相同（為0）得到題解

兩個(gè)數(shù)組的交集 349

給定兩個(gè)數(shù)組?nums1?和?nums2 ，返回 它們的交集?。輸出結(jié)果中的每個(gè)元素一定是 唯一 的。我們可以 不考慮輸出結(jié)果的順序 。

示例 1：

輸入：nums1 = [1,2,2,1], nums2 = [2,2]
輸出：[2]

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> result;
        unordered_set<int> nums1_map(nums1.begin(),nums1.end());
        for(int i=0;i<nums2.size();i++){
            if(nums1_map.find(nums2[i]) != nums1_map.end()){
                //說(shuō)明是交集
                result.insert(nums2[i]);
            }
        }

        return vector<int>(result.begin(),result.end());
    }
};

題解：

由于交集是限制了返回唯一的元素，所以需要有一種數(shù)據(jù)結(jié)構(gòu)既可以存儲(chǔ)相同的元素，又可以返回唯一的值。使用unordered_set 讀寫(xiě)效率是最高的，并不需要對(duì)數(shù)據(jù)進(jìn)行排序，而且還不要讓數(shù)據(jù)重復(fù)，所以選擇unordered_set。

思路是將vector容器中的所有元素，以鍵值對(duì)的方式存入unordered_set容器中，此時(shí)已經(jīng)去重復(fù)了，對(duì)應(yīng)的key只會(huì)存在一個(gè)

利用find的方法判斷是否和nums2匹配，匹配就將元素存入result哈希表容器中，最終轉(zhuǎn)化為vector容器返回即可

兩數(shù)之和1

給定一個(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：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因?yàn)?nums[0] + nums[1] == 9 ，返回 [0, 1] 。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        //分別將數(shù)值作為key，下標(biāo)作為value
        unordered_map<int,int> result;
        for(int i =0;i<nums.size();i++){
            auto turn = result.find(target-nums[i]);
            if(turn!= result.end()){
                //存在則返回
                return {turn->second,i};
            }else{
            result.insert(pair<int,int>(nums[i],i));
            }
        }
        return {};
    }
};

題解：

兩數(shù)之和可以轉(zhuǎn)換為有序存儲(chǔ)的同時(shí)，計(jì)算有沒(méi)有滿足的存在

并且由于需要比較大小，還需要返回下標(biāo)，所以要進(jìn)行map的存儲(chǔ)方式

四數(shù)相加II 454

給你四個(gè)整數(shù)數(shù)組 nums1、nums2、nums3 和 nums4 ，數(shù)組長(zhǎng)度都是 n ，請(qǐng)你計(jì)算有多少個(gè)元組 (i, j, k, l) 能滿足：

0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
?

示例 1：

輸入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
輸出：2
解釋：
兩個(gè)元組如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

class Solution {
public:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> countAB;
        int count = 0;
        for(int i : nums1){
            for(int j : nums2){
                countAB[i+j]++;//儲(chǔ)存起來(lái)數(shù)值對(duì)應(yīng)的次數(shù)
            }
        }

        for(int i : nums3){
            for(int j : nums4){
                //因?yàn)閏++會(huì)自動(dòng)給未創(chuàng)建的鍵值對(duì)自動(dòng)增加
                int target = 0 - (i+j);
                if(countAB.find(target)!=countAB.end()){
                    count += countAB[target];
                }
            }
        }

        return count;
    }
};

題解：

首先考慮存儲(chǔ)每種結(jié)果對(duì)應(yīng)的次數(shù)，結(jié)果不可重復(fù)，所以在這里，最好使用unordered_map來(lái)實(shí)現(xiàn)，

原理是得出nums1和nums2的所有結(jié)果（每一種對(duì)應(yīng)幾種可能），然后再遍歷讓nums3+nums4每一種可能對(duì)應(yīng)的結(jié)果去查詢nums1+nums2的結(jié)果，如果滿足條件（nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0），總結(jié)果加上哈希表中對(duì)應(yīng)的結(jié)果的次數(shù)，最終返回的就是所有結(jié)果的次數(shù)

三數(shù)之和 15

給你一個(gè)整數(shù)數(shù)組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k ，同時(shí)還滿足 nums[i] + nums[j] + nums[k] == 0 。請(qǐng)

你返回所有和為 0 且不重復(fù)的三元組。

注意：答案中不可以包含重復(fù)的三元組。

示例 1：

輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
解釋：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元組是 [-1,0,1] 和 [-1,-1,2] 。
注意，輸出的順序和三元組的順序并不重要。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int left=0,right=0;
        vector<vector<int>> result;//定義返回的數(shù)組
        sort(nums.begin(),nums.end());
        for(int i = 0;i<nums.size();i++){
            if(nums[i]>0){
                break;//說(shuō)明已經(jīng)不可能存在了
            }

            if(i>0 && nums[i] == nums[i-1]){
                continue;//去重，該數(shù)字如果已經(jīng)用過(guò)了，就不再用了
            }

            left = i+1;
            right = nums.size()-1;
             
             
            //基于當(dāng)前的nums[i]進(jìn)行后面所有可能的存入result 
            while(left < right){
                int sumNum = nums[i]+nums[left]+nums[right]; 
                if(sumNum > 0){
                    right--;
                }else if(sumNum < 0){
                    left++;
                }else{
                    result.push_back(vector<int>{nums[i],nums[left],nums[right]});//插入一整個(gè)數(shù)組

                    //去重
                    while(right > left && nums[right] == nums[right-1]){
                        right--;
                    }

                    while(right > left && nums[left] == nums[left+1]){
                        left++;
                    }
                    
                    //當(dāng)去完重之后進(jìn)行原來(lái)的操作--收縮指針--原先的都已經(jīng)用過(guò)了，已經(jīng)為恰好滿足
                    right--;
                    left++;
                }
            }
        }

        return result;
    }
};

題解：

整體上的思路是用雙指針替代了哈希表的算法。因?yàn)樾枰祷匾粋€(gè)二維數(shù)組，并且包括每一種可能，并且還要不重復(fù)，所以在這里使用雙指針去重的思路。

排序整個(gè)數(shù)組，從不重復(fù)的數(shù)字開(kāi)始，作為i元素，之后在后面的區(qū)間里設(shè)置j和k兩個(gè)元素在其各自去重的情況下，計(jì)算和是否滿足為0，j和k兩個(gè)元素作為雙指針從i+1的位置和size-1的位置向中心移動(dòng)，移動(dòng)時(shí)檢測(cè)去重，最終返回結(jié)果

四數(shù)之和 18

給你一個(gè)由 n 個(gè)整數(shù)組成的數(shù)組?nums ，和一個(gè)目標(biāo)值 target 。請(qǐng)你找出并返回滿足下述全部條件且不重復(fù)的四元組?[nums[a], nums[b], nums[c], nums[d]]?（若兩個(gè)四元組元素一一對(duì)應(yīng)，則認(rèn)為兩個(gè)四元組重復(fù)）：

0 <= a, b, c, d?< n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意順序 返回答案 。

示例 1：

輸入：nums = [1,0,-1,0,-2,2], target = 0
輸出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(),nums.end());
        vector<vector<int>> result;
        //順序k，i，left，right
        for(int k =0;k<nums.size();k++){
            if(nums[k] > target && nums[k] >=0){
                //剪枝處理--便于執(zhí)行（只大于不等于--因?yàn)榈扔诳赡芤彩且环N解法 target 0 0 0）
                //因?yàn)橹灰髃，i，left，right互不相同就可以，去重也是為了防止元素間的對(duì)應(yīng)，就比如當(dāng)前這個(gè)元素使用過(guò)了，就不能再使用，兩個(gè)是分開(kāi)的意思
                break;
            }

            if(k>0 && nums[k]==nums[k-1]){
                continue;//去重
            }

            for(int i=k+1;i<nums.size();i++){
                if(nums[i]+nums[k] > target && nums[i]+nums[k] >= 0){
                    //剪枝處理的原理是當(dāng)前的元素大于target，并且兩元素大于0，說(shuō)明后面不可能成立了（都大于0）
                    break;
                }

                //去重一定是從k之后元素開(kāi)始算，因?yàn)檫@也是i的范圍
                if(i>k+1 && nums[i] == nums[i-1]){
                    continue;
                }

                int left = i+1;
                int right = nums.size()-1;

                while(left <right){
                    long targetNum =(long)nums[k]+nums[i]+nums[left]+nums[right];

                    if(targetNum > target){
                        right--;
                    }else if(targetNum < target){
                        left++;
                    }else{
                        result.push_back(vector<int>{nums[k],nums[i],nums[left],nums[right]});

                        while(left <right && nums[right]== nums[right-1]){
                            right--;
                        }
                        while(left <right && nums[left]==nums[left+1]){
                            left++;
                        }

                        //這里再一步的原因是當(dāng)前的rightleft仍為之前的rightleft
                        right--;
                        left++;
                    }
                }
            }
        }

        return result;
    }
};

題解：

總體上的思路和三數(shù)之和相似，但是外面包裹了一層K的判斷，就相當(dāng)于k和i都已經(jīng)確定，兩者分別要進(jìn)行剪枝和去重的操作，內(nèi)部仍然是雙指針的循環(huán)判斷

注意：剪枝和處理的原理

剪枝處理--便于執(zhí)行（只大于不等于--因?yàn)榈扔诳赡芤彩且环N解法 target 0 0 0）
因?yàn)橹灰髃，i，left，right互不相同就可以，去重也是為了防止元素間的對(duì)應(yīng)，就比如當(dāng)前這個(gè)元素使用過(guò)了，就不能再使用，兩個(gè)是分開(kāi)的意思文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-841756.html

到了這里，關(guān)于哈希表C++哈希表詳解（知識(shí)點(diǎn)+相關(guān)LeetCode題目）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！