算法學習：
https://blog.csdn.net/2301_80220607/category_12922080.html?spm=1001.2014.3001.5482
前言：
在之前學習數據結構時我們就學習了哈希表的使用方法，這里我們主要是針對哈希表的做題方法進行講解，都是leetcode上的經典題，各位可以自己做一遍再來看一下，主要抽取了幾個經典的題
目錄
1. 哈希表的基礎知識
1.1 哈希表是什么
1.2 哈希表的作用
1.3 什么時候用哈希表
1.4 哈希表的應用場景
2. 哈希表經典例題
2.1 兩數之和
2.2 存在重復元素||
2.3 字母異位詞分組
3. 總結
1. 哈希表的基礎知識
1.1 哈希表是什么
簡單點來說哈希表就是一個存儲數據的容器，但是能夠對出現的數據進行標記
1.2 哈希表的作用
能夠實現快速查找指定的數據，時間復雜度往往為O(1)
1.3 什么時候用哈希表
頻繁的查找數據時
1.4 哈希表的應用場景
1. 直接使用哈希表這個數據類型
2. 在合適的場景使用數組來模擬哈希表
解釋:
2、3:當我們需要頻繁查找數據的時候我們就可以想到要用哈希表，哈希表的時間復雜度為o(1)，空間復雜度為o(n)同時也要考慮是否可以用二分，二分時間復雜度為o(logn)，也非常快，而且二分沒有時間開銷
4:除了之間使用函數提供給我們的哈希表外，我們也可以用數組模擬創建一個簡易的哈希表，但這種只適用于元素少的情況，比如讓我們統計字符串中各字符出現次數，我們就可以用數組 int hash[26]模擬一下
2. 哈希表經典例題
2.1 兩數之和
1. 兩數之和
給定一個整數數組?nums?和一個整數目標值?target，請你在該數組中找出?和為目標值?target? 的那?兩個?整數，并返回它們的數組下標。
你可以假設每種輸入只會對應一個答案，并且你不能使用兩次相同的元素。
你可以按任意順序返回答案。
示例 1：
輸入：nums = [2,7,11,15], target = 9 輸出：[0,1] 解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
輸入：nums = [3,2,4], target = 6 輸出：[1,2]
示例 3：
輸入：nums = [3,3], target = 6 輸出：[0,1]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只會存在一個有效答案
算法原理：
解法一：暴力枚舉
在這個暴力枚舉中我們來考慮一種新的枚舉思路
比如本題，按照之前的枚舉策略，我們是要讓當前位置(cur)與后面位置的數字依次相加，然后看是否有滿足條件的數字
現在我們來看一種新的枚舉思路，就是讓所有位置的數字，與它前面位置的數字相加，然后判斷是否有滿足條件的兩個數字這樣的思路也能保證讓所有的數兩兩相加，而且在處理一些細節上更有優勢，尤其是本題，下面我們結合本題來感受一下
比如上面我們提到的這個隊列，按照原來的思路，我們先來找一下2后面是否有合適的數字，使得2與其相加等于target，為了減小時間復雜度我們這里要用哈希表的方法，哈希表中存的值是數組中元素和對應的下標<nums[i,i>，但是如果我們是找當前元素后面的值時，我們就需要先提前將數組中所有數字及它們對應的下標先放入哈希表中，但這就會導致一些問題
比如這樣一個數組和target值，如果我們按照原策略先將所有數字和對應下標放入哈希表中的話因為有兩個3，在第一個3及它對應的下標放入哈希表中后，當放第二個3及它對應的下標時，就會把前一個存的3的下標給覆蓋掉，所以我們還需要額外的操作對重復的數字的多個下標進行保存
但是如果我們采取的策略二，我們創建哈希表的時機就會發生一些變化，比如我們現在位置在2，我們是要從前面的位置找合適的數，前面沒有數，所以哈希表中自然也沒有，然后我們可以將2的值及它的下標放入哈希表中，同時讓cur++，這樣做的優化點是什么呢?
此時假如我們再遇到上面的情況(兩個3)，我們在第一個3時査找它前面是否有合適的數(前面的數己經放入哈希表了)時，會發現沒有，然后我們把它放入哈希表中，然后到第二個3，我們發現哈希表中hash[target-3]存有一個下標，我們就找到滿足條件的下標了
假如我們現在的target不是6，而是14，那我們在經過第二個3后，雖然會把哈希表中3對應的下標替換掉，但是仍不影響最終結果
思考一下:其實第二種策略比第一種策略的優化之處就是，策略二在替換一個數的坐標之前，是事先知道這個數字兩兩相加不滿足條件的，所以保留一個與其它數字相加即可，而第一個數字則是在沒考慮這種情況之前就只把重復數字只留下一個
代碼實現：
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> hash;for(int i=0;i<nums.size();i++){if(hash.count(target-nums[i])) return {hash[target-nums[i]],i};hash[nums[i]]=i;}return {-1,-1};}
};2.2 存在重復元素||
219. 存在重復元素 II
給你一個整數數組?nums?和一個整數?k?，判斷數組中是否存在兩個?不同的索引?i?和?j?，滿足?nums[i] == nums[j]?且?abs(i - j) <= k?。如果存在，返回?true?；否則，返回?false?。
示例?1：
輸入：nums = [1,2,3,1], k = 3 輸出：true
示例 2：
輸入：nums = [1,0,1,1], k = 1 輸出：true
示例 3：
輸入：nums = [1,2,3,1,2,3], k = 2 輸出：false
提示：
1 <= nums.length <= 105-109 <= nums[i] <= 1090 <= k <= 105
這道題就可以用上面的思路來解，挺簡單的，可以練練手
代碼實現：
class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int,int> hash;for(int i=0;i<nums.size();i++){if(hash.count(nums[i])&&i-hash[nums[i]]<=k) return true;hash[nums[i]]=i;}return false;}
};2.3 字母異位詞分組
49. 字母異位詞分組
給你一個字符串數組，請你將?字母異位詞?組合在一起。可以按任意順序返回結果列表。
字母異位詞?是由重新排列源單詞的所有字母得到的一個新單詞。
示例 1:
輸入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
輸出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
輸入: strs = [""]輸出: [[""]]
示例 3:
輸入: strs = ["a"]輸出: [["a"]]
提示：
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]?僅包含小寫字母
算法原理：
解釋:
這道題就很考驗我們對哈希表的使用，我們在這里創建的哈希表類型是一個<string，vector<string>>類型的哈希表，我們要做的是把所有的字母異位詞放在一起，那么我們首先就需要判斷哪些詞是字母異位詞，在這里我們有一個很巧的方法去判斷，我們可以把這些字符串排序，字母異位詞排序后是相等的，就如左邊那樣(“eat",“tea“排序后都是“aet")，然后讓排序后的字符串作為key值，字母異位詞放在同一個key值后，最后再從哈希表中把這些字符串數組提取出來即可
代碼實現：
class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string,vector<string>> hash;for(int i=0;i<strs.size();i++){string tmp=strs[i];sort(strs[i].begin(),strs[i].end());hash[strs[i]].push_back(tmp);}vector<vector<string>> ret;for(auto& [x,y]:hash)ret.push_back(y);return ret;}
};3. 總結
以上就是幾個關于哈希表的經典例題，都不算難，哈希表在算法題里出現的比例還是非常高的，一般都是作為一種數據類型存在的，掌握還是很有必要的
本篇筆記：
感謝各位大佬觀看，創作不易，還望各位大佬點贊支持！！
){kind=icon}
