---

前言

哈希表是一個存儲數據的容器，我們如果想要快速查找某個元素，就可以用哈希表，時間復雜度為O（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
只會存在一個有效答案

2.算法原理

暴力解法

我們這里有兩種暴露解法

解法一：

我們先固定right，left從right位置開始，一直尋找到n-1的位置。如果在某個位置發現了left+right=target。我們就返回這兩個下標。否則right++,left=right,繼續尋找。一直走到right=n-1為止。

解法二：

我們同樣先固定right, left從0為止開始，一種走到right-1為止。
中間如果找到滿足條件的就返回，如果找不到就繼續right++,left從0為止開始尋找。一直走到right=n-1為止。

這兩種算法時間復雜度為O(n*n),空間復雜度為O（1）

哈希解法

我們利用哈希表可以快速查找到一個值。

我們遇到一個值，先這個值與前面的值進行判斷，查看是否有滿足條件的。如果不滿足，我們把這個值仍在哈希表中繼續判斷。

如果我們對另一種暴力解法進行優化，我們需要先把整個元素放在哈希表中，再進行二次遍歷，因為可能存在元素相同的情況。
比如nums[ ]={2,4,6,-2,10};taarget=8.
r如果我們先固定4時，快速查找一遍，我們就會找到4，這就重復了，題目要求數組中同一個元素在答案里不能重復出現。
我們就只能另加判斷處理了。

我們采用這種方法，將元素放入hash，同時見擦汗表中是否已經存在了當前元素所對應的目標元素（t-nums[ i ]），提高效率。

時間復雜度為O(n),空間復雜度O(n),空間換時間。

3.代碼編寫

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {//通過一個值快速查找到它的下標unordered_map<int,int>mp;int n=nums.size();for(int i=0;i<n;i++){int x=target-nums[i];if(mp.count(x)){return {i,mp[x]};}mp[nums[i]]=i;}return  {-1,-1};}
};

二、判定是否互為字符重排

1.題目解析

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

示例 1：
輸入: s1 = “abc”, s2 = “bca”
輸出: true

示例 2：
輸入: s1 = “abc”, s2 = “bad”
輸出: false

說明：
0 <= len(s1) <= 100
0 <= len(s2) <= 100

2.算法原理

如果能夠構成重排，哪個字符串中每個字符出現的次數一定是相同的。

解法1:STL中哈希
我們可以用兩個庫里的哈希表實現，s1和s2都丟到哈希表中，遍歷一遍，判斷每個元素的個數是否相同。
這樣做很復雜

解法2:數組模擬哈希表

本道題目明確說明了都是小寫字母，我們可以開一個大小為26的數組，模擬哈希表的完成。我們只需要進行26次判斷就可以了。

解法3:一個哈希表解決

我們可以在第二個解法的基礎上，用一個數組完成。
先把s1中的字母放到數組中，再對s2進行遍歷，如果在數組中，就進行減減操作。如果減到負數了，說明不匹配，返回false。

小優化：如果s1和s2長度都不相同，肯定不符合要求。
時間復雜度O（n),空間復雜度O（26）

3.代碼編寫

class Solution {
public:bool CheckPermutation(string s1, string s2) {//小優化if(s1.size()!=s2.size()){return false;}int hash[26]={0};//s1存元素for(auto&e:s1){hash[e-'a']++;}//s2進行--判斷for(auto&e:s2){if((--hash[e-'a'])<0){return false;}}return true;}
};

三、 字?異位詞分組

1.題目解析

給你一個字符串數組，請你將 字母異位詞 組合在一起。可以按任意順序返回結果列表。
字母異位詞 是由重新排列源單詞的所有字母得到的一個新單詞。

示例 1:
輸入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
輸出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

示例 2:
輸入: strs = [“”]
輸出: [[“”]]

示例 3:
輸入: strs = [“a”]
輸出: [[“a”]]

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

2.算法原理

互為字母異位詞：排完序之后兩個單詞應該完全相同。
我們可以利用這個特性，將單詞按照字典序排序。
排序后，單詞相同的話，就劃分到同一組中。

排序后單詞與原單詞需要互相映射，我們可以用哈希表完成。
相同的單詞劃分到一組，我們可以用vector完成。

3.代碼編寫

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string,vector<string>>mp;//所有字母異位詞分組for(auto&e:strs){//排序string s=e;sort(s.begin(),s.end());mp[s].push_back(e);}//提取結果vector<vector<string>>ret;for(auto& [x,y] : mp){ret.push_back(y);}return ret;}
};

for(auto& [x,y] : mp)注意一下這種寫法

總結

以上就是今天要講的內容。希望對大家的學習有所幫助，僅供參考 如有錯誤請大佬指點我會盡快去改正 歡迎大家來評論~~ 😘 😘 😘