算法练习——哈希表
一：两数之和
题目要求：
解题思路：
常规思路(暴力方法)：定义两个指针遍历，满足条件时，返回下标。
优化版本:如下图
实现代码：
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
unordered_map<int,int> hash;
for(int i = 0; i < nums.size(); i++) {
int tmp = target - nums[i];
if(hash.count(tmp)) {
return {hash[tmp],i};
}
hash[nums[i]] = i;
}
return {-1,-1};
}
};二：判定是否互为字符重排
题目要求：
解题思路：
思路：因为字符串中只包含小写字母，因此定义一个数组来模拟哈希表。分别遍历字符串s2和s1，前者在哈希表中做加法运算，后者做减法运算，当后者被减数变为0时，说明不是字符重排
实现代码：
class Solution {
public:
bool CheckPermutation(string s1, string s2) {
if (s1.size() != s2.size()) {
return false;
}
//统计s2中各个字符出现的次数
int hash[26] = { 0 };
for (auto s : s1) {
hash[s - 'a']++;
}
//比较s1和s2之间字符个数是否相同
for (auto s : s2) {
hash[s - 'a']--;
//出现0说明s1中出现的s2中没有，因此不互为重排字符
if (hash[s - 'a'] < 0) {
return false;
}
}
return true;
}
};三：存在重复元素
题目要求：
解题思路：
思路：本题和第一题的思路相似，定义一个哈希表——unordered_set<int>（因为只需比较是否为相同数字，不需要返回下标），定义一个变量i遍历数组nums，查找当前i位置处的值在哈希表中是否存在，若存在，则返回true，不存在则将当前i位置处的值插入到哈希表中，i++
实现代码：
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> hash;
for(int i = 0; i < nums.size(); i++) {
if(hash.count(nums[i])) {
return true;
}
hash.insert(nums[i]);
}
return false;
}
};四：存在重复元素Ⅱ
题目要求：
解题思路：
思路：本题和第三题思路类似，本题需要用到数组下标，因此用于辅助计算的哈希表应定义为unordered_map<int,int> hash；同样定义变量i遍历数组，查找当前i位置处的值在哈希表中是否存在，且是否满足abs(i - hash[nums[i]]) <= k，若满足，则返回答案，若不满足，则将当前i位置处的值插入到哈希表中
细节:注意到，数组中可能会出现重复数字，但是通过hash[nums[i]] = i;可以覆盖先前的数字对应的下标，因此本题中该细节问题不会对最终答案造成影响，但如果是abs(i - hash[nums[i]]) >= k,就需要处理这个细节问题。
实现代码：
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]) && i - hash[nums[i]] <= k) {
return true;
}
hash[nums[i]] = i;
}
return false;
}
};五：字母异位词分组
题目要求：
解题思路：
思路：本题的大致解法思路和第一题类似，更考察个人对STL接口的熟练度。
定义一个哈希表——unordered_map<string,vector<string>> hash;定义一个变量i遍历字符串数组strs，定义一个字符串遍历tmp，将当前i位置处的字符串赋值给tmp后，通过sort对当前i位置处的字符串进行排列，插入到哈希表中，这样哈希表的second位置处，记录的就是题目所需的最终答案。
最后定义一个字符串数组——vector<vector<string>> ret; 遍历hash，将second处的值插入到ret中得到最终结果。
实现代码：
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> hash;
for(int i = 0; i < strs.size(); i++) {
string tmp = strs[i];
sort(strs[i].begin(),strs[i].end());
hash[strs[i]].push_back(tmp);
}
vector<vector<string>> ret;
for(auto& [x,y] : hash) {
ret.push_back(y);
}
return ret;
}
};