【算法】哈希表相关

【ps】本篇有 5 道 leetcode OJ。 

一、算法简介

        哈希表是一种存储数据的容器，可以快速查找某个元素，其查找的时间复杂度为 O(1)，非常合适需要频繁查找某一个元素的场景。其具体用法为：

• 直接使用底层为哈希表的 STL 容器。
• 用数组模拟简易的哈希表，例如利用数组统计字符串中字符的频次、整型的数据范围很小时映射某些值等。

二、相关例题

1）两数之和

1. 两数之和

.1- 题目解析

        不难想到暴力解法，两层 for 循环将所有组合枚举一遍，即可找到答案。 

        不过，我们还可以用一个 unordered_map 来记录原始数组中每个元素的下标，而要找到和为  target 的两个元素，只需在遍历到原始数组中一个元素 x 时，查询哈希表中是否有值为 target - x 的原始数组元素，有则返回这两个元素作为最终结果。

.2- 代码编写

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）判定是否互为字符重排

面试题 01.02. 判定是否互为字符重排

.1- 题目解析

        如果两个字符串 s1 和 s2 是互为字符重排的，那么它们中的字符相应出现的频次是相同的，我们可以用一个数组来模拟哈希表，统计两个字符串中字符出现的频次。

.2- 代码编写

//写法1：用两个哈希表分别统计后再比对
class Solution {
public:bool CheckPermutation(string s1, string s2) {if(s1.size()!=s2.size())return false;int hash1[26]={0};int hash2[26]={0};for(auto ch:s1)hash1[ch-'a']++;for(auto ch:s2){hash2[ch-'a']++;}for(int i=0;i<26;i++){if(hash1[i]!=hash2[i])return false;}return true;}
};

//写法2：用一个哈希表来统计和比对
class Solution {
public:bool CheckPermutation(string s1, string s2) {if(s1.size()!=s2.size())return false;int hash[26]={0};for(auto ch:s1)hash[ch-'a']++;for(auto ch:s2){hash[ch-'a']--;if(hash[ch-'a']<0)return false;}return true;}
};

3）存在重复元素

217. 存在重复元素

.1- 题目解析

        直接用一个哈希表统计数字出现的频次即可。

.2- 代码编写

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

4）存在重复元素 II

219. 存在重复元素 II

.1- 题目解析

        这道题相较于上一道，哈希表的映射关系不再是 <数字，频次>，而应是 <数字，在原数组中的下标>；返回条件不再是数字出现的频次为 2，而是相同两数的下标之差小于 k。

 

.2- 代码编写

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;}hash[nums[i]]=i;}return false;}
};

5）字母异位词分组

49. 字母异位词分组

.1- 题目解析

        字母异位词之间，字符出现的频次是相同的。我们可以对每一个词通过 ascii 码来进行排序，将排序结果相同的放在一起，即放在一个字符串数组中，由此，我们可以用一个哈希表来存储结果，哈希表中的映射关系是 <排序后的字符串，同组的字母异位词>。

.2- 代码编写

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_back(s);}//构建返回结果vector<vector<string>> ret;for(auto&[x,y]:hash)ret.push_back(y);return ret;}
};