前言
当遇到需要快速判断一个元素是否在集合里出现的时候，就要考虑使用哈希表！
常见的哈希表分为三种：
-
数组：可以将数组下标看作是Key，而下标直接访问的数组元素就是Value；
- 定义：
int record[26] = {0}; - 大小受限，天生契合字母查找问题（最多26/52个元素）
- 定义：
-
集合(set)：最常用的是
unordered_set，它 内部无序 且 不支持重复元素，但增删改查效率最优。- 定义：
unordered_set<int> result_set; - 大小不限，且构建时自动对数值去重，但只能存储一个key；适用于数值查找。
- 此外，如果问题要求集合有序，就用
set；如果要求有序重复，就用multiset
- 定义：
-
映射(map)：最常用的也是
unordered_map，它的key值 内部无序 且 不支持重复，但增删改查效率最优。- 定义：
unordered_map <int, int> map - 特有的键-值对形式；一见到要返回值和地址的，就用
unordered_map
- 定义：
242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意： 若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
思路
- 题中说明只包含小写字母，即定长26，立马想到用数组实现哈希；
- 第一次写先在 t 中判断
hash<0，又在最后判断hash>0，代码段冗余。其实只要最后判断hash!=0即可；
代码实现
class Solution {
public:
bool isAnagram(string s, string t) {
int hash[26] = {0};
int index = 0;
for(int i=0; i<s.size(); i++){
index = s[i] - 'a';
hash[index]++;
}
for(int j=0; j<t.size(); j++){
index = t[j] - 'a';
hash[index]--;
}
for(int k=0; k<25; k++){
if(hash[k] != 0){
return false;
}
}
return true;
}
};
349. 两个数组的交集
给定两个数组 nums1 和 nums2 ，返回它们的 交集。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
思路
- 数组大小未知，且求交集要求元素唯一，明显要用
unordered_set；
重点
- set的相关操作↓↓↓↓
插入删除：
s.insert(a);s.erase(b);长度：s.size();判空：s.empty();首尾：s.begin(); s.end();查找：s.find; # 失败则返回end()
set.find(sum) != set.end()
unordered_set的元素不重复，是指执行100次s.insert(5);，s里也只有一个5
代码实现
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> check(nums1.begin(), nums1.end());
unordered_set<int> result;
for(int i=0; i<nums2.size(); i++){
if(check.find(nums2[i]) != check.end()){
result.insert(nums2[i]);
}
}
return vector<int>(result.begin(), result.end());
}
};
202. 快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
思路
- “无限循环”：本质上还是历史元素的查找问题
重点
- 获取 每个位置 上数字的平方和
n%10获取个位；’
代码实现
class Solution {
public:
int compute(int n){
int sum = 0;
while(n){
sum += (n%10) * (n%10);
n = n/10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> set;
while(n!=1){
int sum = compute(n);
if(set.find(sum)!=set.end()){
return false;
}
set.insert(sum);
n = sum;
}
return true;
}
};
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
思路
- 在当前元素，本质上是找 target - a[i] 是否出现过？→ 就用哈希法！
- 但该问题要查找的元素有两个：1.*target差值； 2.它的下标；→ 要用map！
- 查找 num = target - a[i] ，此时num就可以作为快速查找的
key， - 相应的，其下标则作为
value。
- 查找 num = target - a[i] ，此时num就可以作为快速查找的
重点
-
Map的基本操作： 定义：
unordered_map map;插入：map.insert(pair(nums[i], i)``);查找：map.find(a) != map.end();迭代器(“map的指针”)：auto iter = map.find(a);用迭代器来访问键值元素：键 -it->first();值 -it->second();`# 一个迭代器的例子 for(auto it = hashtable.begin(); it != hashtable.end(); ++it) { cout << "Key: " << it->first << ", Value: " << it->second; } -
Map的格式：以遍历
[2,5,3,6]，target=9为例：map key=2 value=0 key=5 value=1 key=3 value=2 此时遍历至[6]，想要从Map中查找9-6=3，按Key找到，并返回其value=2
代码实现
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for(int i=0; i<nums.size(); i++){
auto iter = map.find(target - nums[i]);
if(iter != map.end()){
return {iter->second, i};
}
map.insert(pair<int,int>(nums[i],i));
}
return {};
}
};
后记
- 数组实现简单（直接下表索引），但处理问题规模也简单（处理稀疏问题浪费大量空间）
- set实现复杂（每次存储都要映射+碰撞），但能处理更复杂的问题（不定长、不重复、无序）
