算法笔记（七）——哈希表

哈希表：一种存储数据的容器；
可以快速查找某个元素，时间复杂度O(1)；
当频繁查找某一个数时，我们可以使用哈希表

1. 创建一个容器（unordered_map）
2. 用数组模拟一个简易哈希表

容器

数据结构	unordered_map	map	unorded_set	set
实现机理	hash	RBT	hash	RBT
元素格式	key+value	key+value	key	key
存储规律	无序	键升序	无序	键升序
元素重复	键不可,值可	键不可,值可	不可重复	不可重复

两数之和

题目：两数之和

思路

• 暴力枚举，初始两个指针 i,j，遍历所有二元组，判断nums[i] + nums[j] == target，时间复杂度：O(N^2)
• 暴力枚举时间复杂度较高的原因是寻找 target - x 的时间复杂度过高，使用哈希表我们可以将查找的时间复杂度降为O(1)，对于每一个 x，我们首先查询哈希表中是否存在target - x

我们可以将元素放入到哈希表中的同时，检查表中是否已经存在当前元素所对应的目标元素，这样就可以避免将元素全部放入到哈希表之后再来二次遍历

C++代码

class Solution 
{
public:vector<int> twoSum(vector<int>& numbers, int target) {unordered_map<int, int> hash; // 【数，下标】for(int i = 0; i < numbers.size(); i++){if(hash.find(target - numbers[i]) != hash.end())return {i, hash[target - numbers[i]]};hash[ numbers[i] ] = i;}return {};}
};

判定是否互为字符重排

题目：判定是否互为字符重排

思路

• 如果两长度不相等，直接返回fasle
• 创建一个hash表，对于s1我们添加到hash表中，对于s2中的每个字符如果hash中存在，那么我们删除一个，最后单独遍历一遍hash表，如果其值不等于零也就意味值s1或s2中元素数量不匹配，也就不发重排。

C++代码

class Solution 
{
public:bool CheckPermutation(string s1, string s2) {if(s1.size() != s2.size()) return false;unordered_map<char, int> hash;for(auto ch : s1) hash[ch]++;for(auto ch : s2) hash[ch]--;for(auto x : hash) if(x.second != 0)return false;return true;}};

存在重复元素

题目：存在重复元素

思路

• 创建一个hash表，插入元素；
• 遍历hash表，如果某个元素个数不等于1，返回true；遍历完后如果没有返回，则返回false

C++代码

class Solution 
{
public:bool containsDuplicate(vector<int>& nums) {unordered_map<int, int> hash;for(auto x : nums)hash[x]++;for(auto x : hash)if(x.second != 1) return true;return false;}
};

存在重复元素 II

题目：存在重复元素 II

思路

• 和两数之和一样，只需在遇到相同元素时相减判断；

C++代码

class Solution 
{
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {// 【数，下标】unordered_map<int, int> hash;int n = nums.size();for(int i = 0; i < n; i++){// 如果当前元素已经在 hash 中存在if(hash.count(nums[i])){// 判断下标是否满足要求if(i - hash[nums[i]] <= k)return true;}hash[nums[i]] = i;}return false; // 遍历完数组没有发现符合条件的重复元素，返回 false}
};

字母异位词分组

题目： 字母异位词分组

思路

• 判断两个字符串是否为字母异位词（排序）
• unordered_map<string, vector<string>> hash;

C++代码

class Solution 
{
public:vector<vector<string>> groupAnagrams(vector<string>& strs){unordered_map<string, vector<string>> hash;for(auto& s : strs){string tmp = s;sort(tmp.begin(), tmp.end());hash[tmp].push_bacck(s);}vector<vector<string>> ret;for(auto& [k, v] : hash){ret.push_bacck(y);} return ret;}
};