一、std::unordered_map
std::unordered_map 是一个关联容器，它存储键值对，并且使用哈希表来组织数据。因此，它提供了快速的查找、插入和删除操作，平均时间复杂度为 O(1)。
1.主要特性
- 无序性：元素在容器中的位置并不按照插入顺序或键的顺序排列，而是根据哈希值分布。
- 快速查找：平均情况下，查找、插入和删除操作的时间复杂度为 O(1)。
- 键唯一性：每个键在
std::unordered_map中是唯一的。
2.基本操作
- 插入元素：使用
insert方法或operator[]。 - 查找元素：使用
find方法或operator[]（如果键不存在，operator[]会插入一个默认构造的值）。 - 删除元素：使用
erase方法。 - 遍历元素：可以使用迭代器遍历所有元素。
二、示例题目
1.两数之和 . - 力扣（LeetCode）
给定一个整数数组 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]
解法(哈希表)
算法思路:
- 如果我们可以事先将「数组内的元素」和下标」绑定在一起存入「哈希表」中，然后直接在哈希表中查找每一个元素的 target- nums[i],就能快速的找到「目标和的下标」。
- 这里有一个小技巧，我们可以不用将充素全部放入到哈希表之后，再来二次遍历(因为要处理元素相同的情况)。而是在将元素放入到哈希表中的「同时」，直接来检查表中是否已经存在当前元素所对应的目标元素(即 target-nums[i])。如果它存在，那我们已经找到了对应解，并立即将其返回。无需将元素全部放入哈希表中，提高效率。
- 因为哈希表中查找无素的时间复杂度是 0(1)，遍历一遍数组的时间复杂度为 O(N)，因此可以将时间复杂度降到O(N）。
这是一个典型的「用空间交换时间」的方式。
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 x=target-nums[i];
if(hash.count(x))
return {hash[x],i};
hash[nums[i]]=i;
}
return {-1,-1};
}
};2.判断是否互为字符重排. - 力扣（LeetCode）
给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
示例 1：
输入: s1= "abc", s2= "bca" 输出: true
示例 2：
输入: s1= "abc", s2= "bad" 输出: false
解法(哈希表)
算法思路:
1.当两个字符串的长度不相等的时候，是不可能构成互相重排的，直接返回 false;
2.如果两个字符串能够构成互相重排，那么每个字符串中「各个字符」出现的「次数」一定是相同的。因此，我们可以分别统计出这两个字符串中各个字符出现的次数，然后逐个比较是否相等即可。这样的话，我们就可以选择「哈希表」来统计字符串中字符出现的次数。
class Solution {
public:
bool CheckPermutation(string s1, string s2)
{
if(s1.size()!=s2.size())
return false;
int hash[26];
for(int i=0;i<s1.size();i++)//统计第一个字符串的信息
{
hash[s1[i]-'a']++;
}
for(int j=0;j<s2.size();j++)//扫描第二个字符串，看看是否能重排
{
hash[s2[j]-'a']--;
if(hash[s2[j]-'a']<0)//小于0证明有第一个字符串不存在的字符
return false;
}
return true;
}
};3.存在重复元素. - 力扣（LeetCode）
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入：nums = [1,2,3,1]
输出：true
解释：
元素 1 在下标 0 和 3 出现。
示例 2：
输入：nums = [1,2,3,4]
输出：false
解释：
所有元素都不同。
示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true
解法(哈希表)
算法思路:
分析一下题目，出现「至少两次」的意思就是数组中存在着重复的元素，因此我们可以无需统计元素出现的数目。仅需在遍历数组的过程中，检查当前元素「是否在之前已经出现过」即可。因此我们可以利用哈希表，仅需存储数「组内的元素」。在遍历数组的时候，一边检查哈希表中是否已经出现过当前元素，一边将元素加入到 哈希表中。
class Solution {
public:
bool containsDuplicate(vector<int>& nums)
{
unordered_map<int,int> hash;
for(int x:nums)
{
if(hash.count(x))
return true;
else
hash[x]++;
}
return false;
}
};4.存在重复元素Ⅱ. - 力扣（LeetCode）
给你一个整数数组 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
解法(哈希表)
算法思路:
解决该问题需要我们快速定位到两个信息
两个相同的元素;
这两个相同元素的下标。
因此，我们可以使用「哈希表」，令数组内的元素做 key 值，该元素所对应的下标做 val 值，将「数组元素」和「下标」绑定在一起，存入到「哈希表」中。
思考题:
如果数组内存在大量的「重复元素」，而我们判断下标所对应的元素是否符合条件的时候，需要将不同下标的元素作比较，怎么处理这个情况呢?
答:这里运用了一个「小贪心」。
我们按照下标「从小到大」的顺序遍历数组，当遇到两个元素相同，并且比较它们的下标时，这两个下标一定是距离最近的，因为:
- 如果当前判断符合条件直接返回 true，无需继续往后查找。.
- 如果不符合条件，那么前一个下标一定不可能与后续相同元素的下标匹配(因为下标在逐渐变大)，那么我们可以大胆舍去前一个存储的下标，转而将其换成新的下标，继续匹配。
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]))
{
int j=hash[nums[i]];
if(abs(i-j)<=k)
return true;
else
hash[nums[i]]=i;
}
else
{
hash[nums[i]]=i;
}
}
return false;
}
};5.字母异位词分组. - 力扣（LeetCode）
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""] 输出: [[""]]
示例 3:
输入: strs = ["a"] 输出: [["a"]]
解法(哈希表+排序)
算法思路:
互为字母异位词的单词有一个特点:将它们「排序」之后，两个单词应该是「完全相同」的。所以，我们可以利用这个特性，将单词按照字典序排序，如果排序后的单词相同的话，就划分到同一组中。
这时我们就要处理两个问题:
- 排序后的单词与原单词需要能互相映射;
- 将排序后相同的单词，「划分到同一组」;
利用语言提供的「容器」的强大的功能就能实现这两点:
- 将排序后的字符串(string)当做哈希表的 key 值;
- 将字母异位词数组(string[])当成 val 值。
定义一个「哈希表」即可解决问题。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
unordered_map<string,vector<string>> hash;
for(string x:strs)
{
string str=x;
sort(x.begin(),x.end());
hash[x].push_back(str);
}
vector<vector<string>> vv;
for(auto x:hash)
{
vv.push_back(x.second);
}
return vv;
}
};从这道题我们可以拓展一下视野，不要将容器局限于基本类型，它也可以是一个容器嵌套另一个容器的复杂类型。
