哈希表 part01
今日任务
● 哈希表理论基础
● 242.有效的字母异位词
● 349. 两个数组的交集
● 202. 快乐数
● 1. 两数之和
链表理论基础
文章链接：https://programmercarl.com/哈希表理论基础.html#哈希表
重点：
-
哈希表是根据关键码的值而直接进行访问的数据结构。
-
一般哈希表都是用来快速判断一个元素是否出现集合里。
-
哈希表的关键是哈希函数。哈希函数如下图所示，通过hashCode把名字转化为数值，一般hashcode是通过特定编码方式，可以将其他数据格式转化为不同的数值，这样就把学生名字映射为哈希表上的索引数字了。
4.哈希函数映射到数组的同一个下标可能会产生哈希碰撞。如图所示，小李和小王都映射到了索引下标 1 的位置，这一现象叫做哈希碰撞。
5.哈希碰撞可以用两种方法解决：第一是拉链法，冲突结点可以转换成链表结构存储。第二是线性检测法，需要有足够大的尺寸，让冲突结点存到其他地方去。
6.C++中的哈希表实现
Problem: 242. 有效的字母异位词
思路
首先我们因为字母是有限个，所以我们可以利用数组去存储。一共26个字母，所以数组大小为26，并且不用记住字母下标，只要计算与'a'的相对距离即可。遍历一遍数组a，遍历一遍数组b，最后我们通过查看结果数组即可判断是否是异位词。
解题方法
哈希表
Code
//时间复杂度: O(n)
//空间复杂度: O(1)
class Solution {
public:
bool isAnagram(string s, string t) {
int count[26] ={0};
for(int i = 0; s[i] != '\0';i++){
count[ (int)s[i]-'a']++;
}
for(int i = 0; t[i] != '\0';i++){
count[ (int)t[i]-'a']--;
}
for(int i = 0; i < (sizeof (count) / sizeof (count[0]));i++){
if(count[i] != 0) return false;
}
return true;
}
};
Problem: 349. 两个数组的交集
思路
首先，用一个哈希表set去初始化第一个数组，用一个空哈希表专门保存结果数据，然后遍历第二个数组里的所有数字，如果有数字出现在哈希表中就插入结果哈希表中，最后返回这个结果哈希表。
解题方法
哈希表
Code
//时间复杂度: O(mn)
//空间复杂度: O(n)
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> res; // 存放结果，之所以用set是为了给结果集去重
unordered_set<int> nums_set(nums1.begin(), nums1.end());
for(auto num : nums2){
if(nums_set.find(num) != nums_set.end()){
res.insert(num);
}
}
return vector<int>(res.begin(),res.end());
}
};
Problem: 202. 快乐数
思路
首先我们每求到一个数字的快乐数，先判断这个快乐数曾经在哈希表出现过，如果出现过，那么说明这个数的求快乐数的过程会进入死循环，永远求不到快乐数==1的情况，就立刻返回false。如果没出现过就将该结果插入哈希表。
解题方法
先判断是否重复，再插入，如果有重复直接返回false，快乐数==1退出循环。
Code
//时间复杂度: O(logn)
//空间复杂度: O(logn)
class Solution {
public:
int getSum(int n){
int sum = 0;
while(n){
sum+=(n%10)*(n%10);
n = n/10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> sum_res;
while(1){
int sum = getSum(n);
if(sum == 1){
return true;
}
if(sum_res.find(sum) != sum_res.end()){
return false;
}else{
sum_res.insert(sum);
}
n = sum;
}
}
};
Problem: 1. 两数之和
思路
为什么会想到用哈希表？因为当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。
哈希表为什么用map？因为我们问题要求我们返回的是下标。
本题map是用来存什么的？键存的是数值，方面find函数查找，值存的的下标，通过迭代器返回。
解题方法
哈希表
Code
/*
用unordered_map不是不能存储两个相同的key吗，那如果数组里两个出现相同的两个元素都要存储会怎么样呢？
注意它存入的方式，它是在循环的过程中边检验边存的，如果没有对应的数字就存入map，如果有就计数，这样不会遇到重复的
*/
//时间复杂度: O(n)
//空间复杂度: O(n)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> res;//创建一个map用来查找结果
for(int i = 0; i < nums.size(); i++){
//这里必须先判断再插入数据，因为如果先插入的话就会将自己算一遍
auto iter = res.find(target-nums[i]);
if(iter!=res.end()){
return {iter->second,i};
}
else{
res.insert(pair<int,int>(nums[i],i));
}
}
return {};
}
};