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 - ‘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)。

1. class Solution {
2. public:
3.     bool isAnagram(string s, string t) {
4.         int record[26] = {0};
5.         for (int i = 0; i < s.size(); i++)
6.         {
7.             record[s[i] - 'a']++;
8.         }
9.         for (int i = 0; i < t.size(); i++)
10.         {
11.             record[t[i] - 'a']--;
12.         }
13.         for (int i = 0; i < 26; i++)
14.         {
15.             if(record[i] != 0)
16.             {
17.                 return false;
18.             }
19.         }
20.         return true;
21.     }
22. };

复制代码

349. 两个数组的交集

题目：给定两个数组，编写一个函数来盘算它们的交集。力扣题目链接
思路：留意题目特意阐明：输出效果中的每个元素一定是唯一的，也就是说输出的效果的去重的， 同时可以不考虑输出效果的次序
std::set和std::multiset底层实现都是红黑树，std::unordered_set的底层实现是哈希表， 使用unordered_set 读写服从是最高的，并不需要对数据进行排序，而且还不要让数据重复，所以选择unordered_set。

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

复制代码

   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会重复出现，这对解题很紧张！【对哈希表的算法我也不大会，只能说是多积累吧】

1. class Solution {
2. public:
3.     int getSum(int n) {
4.         int sum = 0;
5.         while(n){
6.             sum += (n % 10) * (n % 10);
7.             n /= 10;
8.         }
9.         return sum;
10.     }
11.     bool isHappy(int n) {
12.         unordered_set<int> set;
13.         while(1){
14.             int sum = getSum(n);
15.             if(sum == 1)
16.             {
17.                 return true;
18.             }
19.             if(set.find(sum) != set.end())
20.             {
21.                 return false;
22.             }
23.             else
24.             {
25.                 set.insert(sum);
26.             }
27.             n = sum;
28.         }
29.     }
30. };

复制代码

1.两数之和

题目：
给定一个整数数组 nums 和一个整数量标值 target，请你在该数组中找出 和为目的值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
思路：用unordered_map【最高效】,遍历所有元素，并将数值和下标存入key和value。target - 当前元素的值，得到一个变量，去map中find，看看是否有目的值，有则返回，无则继承循环，直到竣事。

1. class Solution {
2. public:
3.     vector<int> twoSum(vector<int>& nums, int target) {
4.          std::unordered_map <int,int> map;
5.         for(int i = 0; i < nums.size(); i++) {
6.             // 遍历当前元素，并在map中寻找是否有匹配的key
7.             auto iter = map.find(target - nums[i]);
8.             if(iter != map.end()) {
9.                 return {iter->second, i};
10.             }
11.             // 如果没找到匹配对，就把访问过的元素和下标加入到map中
12.             map.insert(pair<int, int>(nums[i], i));
13.         }
14.         return {};
15.     }
16. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。