目录
理论基础
242.有效的字母异位词
349.两个数组的交集
202.快乐数
1.两数之和
理论基础
哈希表用来判断一个元素是否出现在集合里（判断一个元素是否出现过）。牺牲空间换时间，会使用到额外的空间。
又称散列表，key-value,根据key值来访问
（数组就是简单的哈希表，但是数组的大小不是无限开辟的）
哈希函数：
hashCode将其他数据格式转为数值。使用取模tableSize来避免hashCode得到的数值大于了哈希表的大小。
哈希碰撞：
学生的数量大于哈希表大小。大于1个，映射到了同一个索引位置。
拉链法：发生冲突的元素存储在这个位置的链表中
线性探测法：冲突元素相应存在后面的空位置上。数据规模dataSize需大于tableSize，否则没有空位。
三种哈希结构：
（表格中除第二行写全外，其他两行与第一行对比后只在不同处写）
（对于map来说，有序重复数值修改指的都是key，value不管）
（考虑顺序（根据题目）：unordered_set -> set -> multiset）（首先考虑unordered，它的查询和删除效率最优，如果还需要有序，就用set，如果要求不仅有序还要有重复数据，就用multi）
| 集合set（映射map） | 底层实现 | 是否有序 | 数值是否可重复 | 能否更改数值 | 查询效率 | 增删效率 |
| std::set | 红黑树 | 有序 | 否 | 否 | O(logn) | O(logn) |
| std::multiset | 是 | |||||
| std::unordered_set | 哈希表 | 无序 | O(1) | O(1) |
红黑树是一种平衡二叉搜索树，故key值有序，但key不可修改，只能增删
- 数组：大小有限制，如果元素很少，哈希值太大会造成内存空间的浪费
- set集合：只有key，适用于哈希值很大或者哈希值比较少，特别分散，跨度非常大的情况
- map映射：有key和value
242.有效的字母异位词
解决办法：
1. 暴力解法：两个for循环嵌套，定义一个布尔变量，用来实时判断是否找到相同字符串，若找到则true,未找到则false,最后根据该布尔变量的值来return。
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.length() != t.length()) {
return false;
}
for (int i = 0; i < s.length(); i++) {
bool find = false;
for (int j = 0; j < t.length(); j++) {
if (s[i] == t[j]) {
t.erase(j, 1);
find =true;
break;
}
}
if (!find) {
return false;
}
}
return true;
}
};时间复杂度O(n^2）
2. 哈希表：
判断相同字符是否出现过，用哈希表。（判断某个元素是否出现在集合里）
这里巧妙利用字符a到字符z的ASCII码值是26个连续的数值（数据量小，数组），将字符映射到数组也就是哈希表的索引下标上，并借助减去'a'，不需要记住字符a的ASCII码值，让其对应上数组从0开始的索引，即定义一个大小为26的数组。s中对应字母+1，t中在数组对应字母-1，若最后数组所有元素均为0，则s,t中字母元素及对应个数相同。（数组来记录每个字符出现的次数）
都是a-z的小写字母，数值小且可控，用数组来做映射就可以了。
Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) { // 长度不同则直接不可能为字母异位词
return false;
}
int hash[26] = {0}; // 在函数内部声明数组时，显式的对元素初始化
for (int i = 0; i < s.size(); i++) {
hash[s[i] - 'a']++; // 相对数值，不需要记住字符a确切的ASCII码值
hash[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (hash[i] != 0) {
return false;
}
}
return true;
}
};时间复杂度O(n)
空间复杂度O(1)
349.两个数组的交集
解决办法：
需判断第二个数组里的元素是否出现在第一个数组去重后的集合里，故用哈希表。（判断某个元素是否出现在集合里）
1. 数组解法（和上一题类似）（元素题目给了限制，故数组大小不超过1000，0<=nums[1],nums[2]<=1000）
使用unordered_set来定义result，实现自动降重（题目要求了输出结果中每个元素唯一，不考虑输出结果的顺序）
return vector<int>(result_set.begin(), result_set.end());最后把set转化成vector
hash直接初始化为一个固定大小数组
增强for循环更简洁
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
int hash[1005] = {0}; //稍大一点即可
// for (int i = 0; i < nums1.size(); i++) {
// hash[nums1[i]] = 1;
// }
// for (int i = 0; i < nums2.size(); i++) {
// if (hash[nums2[i]] == 1) {
// result.insert(nums2[i]);
// }
// }
for (int num : nums1) { // 增强for循环
hash[num] = 1;
}
for (int num : nums2) {
if (hash[num] == 1) {
result_set.insert(num); // 会自动降重
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};时间复杂度O(n + m)
空间复杂度O(n) (result_set最坏情况与输入数组成线性关系）
2. set解法 （题目未限制数值的大小，可能会非常大；哈希值比较少、特别分散、跨度非常大。最好也用set，毕竟此时用数组就会造成极大的空间浪费）（但如果限制了数值大小，就最好用数组了，因为set占用空间会比数组大，同时速度也比数组慢，set把数值映射到key上都要做hash计算）
find(num)函数返回一个迭代器，指向nums_set集合中找到的元素，如果没有找到，则返回nums_set.end()，即集合的尾后迭代器。
nums_set（hash）初始化为nums1，大小就不是固定的，如果数值非常大，也不会出现像数组那样一堆空间被浪费情况
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> nums_set(nums1.begin(), nums1.end()); // 初始化为nums1中的元素
for (int num : nums2) {
if (nums_set.find(num) != nums_set.end()) { // nums2的元素是否在nums_set里
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};时间复杂度O(n + m) nums1储存到numsz-set为n，find为1，nums2遍历为m，k(k<=n)是最后要把set转成vector
空间复杂度O(n)文章来源：https://www.toymoban.com/news/detail-831531.html
202.快乐数
解决办法：
题提到会无限循环，即在求和过程中sum重复出现，故需判断sum是否重复出现，故用哈希表。（快速判断一个元素是否出现在集合里）
注意如何取数值各个位来进行单数操作。
class Solution {
public:
// 取数值各个位上的单数之和
int getSum(int n) {
int sum = 0;
while(n) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
// 判断重复出现否，故用unordered_set自动降重
unordered_set<int> nums_set;
// while(1)无限循环
while (1) {
int sum = getSum(n);
if (sum == 1) {
return true;
}
// 若sum已出现过，则进入无限循环了
if (nums_set.find(sum) != nums_set.end()) {
return false;
} else {
nums_set.insert(sum);
}
// n又等于新的sum值
n = sum;
}
}
};时间复杂度O(logn)
空间复杂度O(logn)
（主要是getSum函数，对n的每一位进行一次操作，总共有log10(n)+1位；find查找和insert操作都是O(1)）
1.两数之和
解决办法：
本题解题思路为每遍历一个数后，查看前面（单独存放在一个集合）是否有遍历到与本数相加能得到target的数，如果有，就找到了匹配对，如果没有，就把当前遍历数添加到集合里。（注意这里符合的两个整数并不一定是相邻的）
- 为什么用哈希表：要判断前面是否有遍历到符合要求的数。（判断某个元素是否出现过）
- 为什么用map：本题除了要找到该元素，还要找到该元素的下标。map映射有key和value
- 本题的map作用：用来存放已经遍历过的元素，进而判断是否已遍历过符合要求的数
- key,value分别是什么：这里要找的是某个元素是否出现过，那么就用key来保存元素(map就是能在短时间内找到key是否出现过）,value来保存下标。
- unordered_map：本题不需要有序，且同一个元素不能重复出现
注意map的一些语法以及返回两个下标的写法
auto：自动推导变量类型，不然这里写成unordered_map<int, int>
pair<int, int>：模板类，表示包含两个int类型元素的有序对，这里就是将元素和对应下标打包成有序对并返回。可用于存储两个不同类型的值，拥有公共成员变量first和second
{iter->second, i}：花括号{}进行列表初始化，这个向量会被创建并直接作为函数的返回值。iter->second指的是map中差值元素对应的下标，i是当前元素的下标
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map;
for (int i = 0; i < nums.size(); i++) {
int s = target - nums[i]; // 要查找的前面是否出现过的数
auto iter = map.find(s);
// 遍历当前元素，并在map中查找是否有匹配的key
if (iter != map.end()) {
return {iter->second, i};
} else {
map.insert(pair<int, int>(nums[i], i));
}
}
return {};
}
};时间复杂度O(n)
空间复杂度O(n)
由于相关知识缺乏，基本上没啥思路，故就不写第一思路和解决状态了，主要就直接写解决办法了。文章来源地址https://www.toymoban.com/news/detail-831531.html
到了这里，关于力扣 | 哈希表1 | 242.有效的字母异位词，349.两个数组的交集，202.快乐数，1.两数之和的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
