一、哈希介紹
是什么
存儲數據的容器
什么用
快速查找某個元素
什么時候用哈希表
頻繁的查找某一個數的時候
怎么用哈希表
（1）容器（哈希表）
（2）用數組模擬哈希表（字符串的字符，數據范圍很小的時候）
二、題目
1、兩數之和
兩數之和
（1）題目
（2）解題思路
解題思路一：雙指針，遍歷整個數組，把符合條件的返回
解題思路二：用哈希表，將數組下標和值存起來，在遍歷數組的時候，在哈希表中尋找目標值和當前遍歷的值的差值
（3）代碼實現
解法一：
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {for(int i = 0; i<nums.size(); i++){for(int j = i+1; j<nums.size(); j++){if(nums[i]+nums[j]==target){return{i,j};}}}return {-1,-1};}
};
class Solution
{
public:vector<int> twoSum(vector<int>& nums, int target) {for(int i = 0; i<nums.size();i++){for(int j = 0; j<i;j++){if(nums[i]+nums[j] == target){return {i,j};}}} return {-1,-1}; }
};解法二：
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int,int> hash;for(int i = 0 ; i<nums.size();i++){int t = target - nums[i] ;if(hash.count(t)){return {hash[t], i};}hash[nums[i]] = i;}return {-1,-1};}
};2、判斷數組是否重排
?判斷數組是否重排
?（1）題目
（2）解題思路
我們可以用數組模擬哈希表，開一個數為26的數組，首先遍歷其中一個字符串將每一個字母-'0'的位置--，然后再遍歷另外一個字符串將每一個字母的-'0'的字母++，最后遍歷數組如果存在不是0的數就不是重排
（3）代碼書寫
class Solution
{
public:bool CheckPermutation(string s1, string s2) {if(s1.size()!=s2.size()){return false;}int nums[26]={0};for(int i = 0; i < s1.size(); i++){nums[s1[i]-'a']++; nums[s2[i]-'a']--; }for(int j = 0; j<26;j++){if(nums[j]!=0)return false;}return true;}
};3、存在重復元素
存在重復元素
（1）題目
?（2）解題思路
? ? ? ?我們創立一個哈希表，遍歷nums，如果存在數組中的值則返回true，不存在數組中的則插入
（3）代碼實現
class Solution
{
public:bool containsDuplicate(vector<int>& nums) {unordered_set<int> hash;for(auto x: nums)if(hash.count(x))return true;else hash.insert(x);return false;}
};4、存在重復元素二
存在重復元素二
?（1）題目
（2）解題思路
? ?創建一個哈希表，遍歷nums如果哈希表中存在該下標的值，判斷該下標和原先所存儲的小表達差值是否小于k，如果是，返回true，否則覆蓋下標，如果哈希表中部存在該下標的值，則插入
（3）代碼實現
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])) {if(i - hash[nums[i]]<=k){return true;}else{hash[nums[i]] = i;}}else{hash[nums[i]] = i;}}return false;}
};5、字母異位詞分組
字母異位詞分組
（1）題目
?
（2）解題思路
我們可以創立一個哈希表string ，vector<string> 然后遍歷strs，將他的值排序后如果hash表中含有，插入到vector<string>中
（3）代碼實現
class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string ,vector<string>> hash;for(auto&e: strs){string tmp = e;sort(tmp.begin(),tmp.end());hash[tmp].push_back(e);}vector<vector<string>> ret;for(auto &[x,y] : hash){ret.push_back(y);}return ret;}};
)
