Hash table类算法【leetcode】

哈希表中关键码就是数组的索引下标，然后通过下标直接访问数组中的元素

那么哈希表能解决什么问题呢，一般哈希表都是用来快速判断一个元素是否出现集合里。

例如要查询一个名字是否在这所学校里。

要枚举的话时间复杂度是O(n)，但如果使用哈希表的话， 只需要O(1)就可以做到。

我们只需要初始化把这所学校里学生的名字都存在哈希表里，在查询的时候通过索引直接就可以知道这位同学在不在这所学校里了。

将学生姓名映射到哈希表上就涉及到了hash function ，也就是哈希函数。

242.有效的字母异位词

题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。力扣题目链接

思路：定义一个数组叫做record用来上记录字符串s里字符出现的次数。

需要把字符映射到数组也就是哈希表的索引下标上，因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下标0，相应的字符z映射为下标25。

再遍历 字符串s的时候，只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。 这样就将字符串s中字符出现的次数，统计出来了。

那看一下如何检查字符串t中是否出现了这些字符，同样在遍历字符串t的时候，对t中出现的字符映射哈希表索引上的数值再做-1的操作。

那么最后检查一下，record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。

最后如果record数组所有元素都为零0，说明字符串s和t是字母异位词，return true。

时间复杂度为O(n)，空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。

class Solution {
public:bool isAnagram(string s, string t) {int record[26] = {0};for (int i = 0; i < s.size(); i++){record[s[i] - 'a']++;}for (int i = 0; i < t.size(); i++){record[t[i] - 'a']--;}for (int i = 0; i < 26; i++){if(record[i] != 0){return false;}}return true;}
};

349. 两个数组的交集

题目：给定两个数组，编写一个函数来计算它们的交集。力扣题目链接

思路：注意题目特意说明：输出结果中的每个元素一定是唯一的，也就是说输出的结果的去重的， 同时可以不考虑输出结果的顺序

std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写效率是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> result_set; // 存放结果，之所以用set是为了给结果集去重unordered_set<int> nums_set(nums1.begin(), nums1.end());for (int num : nums2) {// 发现nums2的元素 在nums_set里又出现过if (nums_set.find(num) != nums_set.end()) {result_set.insert(num);}}return vector<int>(result_set.begin(), result_set.end());}
};

 unordered_set<int> nums_set(nums1.begin(), nums1.end()); 解释：

 这行代码将 nums1 中的所有元素插入到 nums_set 中。nums1.begin() 和 nums1.end() 分别是 nums1 向量的起始迭代器和结束迭代器，表示整个 nums1 向量的范围。

 for (int num : nums2) 解释：

是 C++ 中的一种范围基于的循环（range-based for loop）语法。这种语法用于遍历容器或数组中的每个元素，而无需显式地使用迭代器或索引。它使代码更加简洁和易读。

具体来说，for (int num : nums2) 的含义是：

• int num：声明一个变量 num，其类型为 int。在每次循环迭代中，num 会依次取 nums2 中的每个元素的值。
• nums2：要遍历的容器或数组。在这个例子中，nums2 是一个 std::vector<int> 类型的向量。

因此，for (int num : nums2) 的完整意思是：对于 nums2 中的每个元素，将该元素的值赋给 num，然后执行循环体内的代码。

在 C++ 中，unordered_set（以及 set、map 等关联容器）提供了一个成员函数 find，用于查找容器中是否存在某个特定的键。find 函数的返回值是一个迭代器，指向找到的元素；如果未找到该元素，则返回一个特殊的迭代器，通常称为“结束迭代器”（end iterator），即 end()。 

第202题. 快乐数

题目：

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

思路：题目中说了会 无限循环，那么也就是说求和的过程中，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<int> set;while(1){int sum = getSum(n);if(sum == 1){return true;}if(set.find(sum) != set.end()){return false;}else{set.insert(sum);}n = sum;}}
};