目录

哈希表原理：

哈希的分类

哈希集合：

哈希映射：

哈希STL函数的使用：

1：存在重复元素

 2：只出现一次的数字

3：两个数组的交集

4：快乐数

5：赎金信（字母异位词的开始）

6：字母异位词分组

7：找到字符串中所有字母的异位词（滑动窗口+哈希）

8：两数之和

9：四数相加||

---

哈希表原理：

哈希的分类

可以把它简单地理解为数组，但其实它更像python中的字典

哈希集合：

头文件：#include <unordered_set>

创建哈希集合：unordered_set<type> set;

个人理解：

不如创建一个数组，因为创建一个哈希消耗的内存比较大= =，这里数组和哈希集合承担的作用其实是一样的= =

哈希映射：

头文件：#include <unordered_map>

创建哈希映射：  unordered_map<type, type> map;

个人理解：

这个就是python的字典，第一个type是键(key)，第二个type是值(value)，通过键来查询值

可以理解为：在药房，药师通过看抽屉的标签来查询抽屉的药品，标签就是键，药品就是值

所以，哈希相当于用空间换时间，查询哈希的值，要比遍历数组查询值所需的时间要短.

哈希STL函数的使用：

引用哈希集合时的应用：

#include <unordered_set>                // 当使用set时引用的模板库
#include<iostream>
using namespace std;
int main() {// 创建一个哈希集合unordered_set<int> hashset;   // 插入新的关键字hashset.insert(3);hashset.insert(2);hashset.insert(1);// 删除关键字hashset.erase(2);// 判断关键字是否在哈希集合中，如果在方法返回负数。如果在集合中返回真，否则返回假if (hashset.count(2) <= 0) {cout << "关键字2不在哈希集合中" << endl;}// 得到哈希集合的大小cout << "The size of hash set is: " << hashset.size() << endl; // 遍历哈希集合，注意要以指针的形式for (auto it = hashset.begin(); it != hashset.end(); ++it) {cout << (*it) << " ";}cout << "are in the hash set." << endl;// 清除哈希集合hashset.clear();// 判断哈希结合是否为空if (hashset.empty()) {cout << "hash set is empty now!" << endl;}
}

引用哈希表的应用：

#include<unordered_map>
#include<iostream>
using namespace std;
int main()
{unordered_map<int,int>map;//创建哈希表map[4] = 14;//直接赋值map[5] = 15;cout << map[4];//输出14//通过insert()函数来添加元素map.insert({ 5,15 });//参数为（键，值）map.insert({ 5,16 });cout << map[5];  //结果为15->一个下标只能对应一个值//复制，重新构造一张新的哈希表unordered_map<int, int> map{ {1,10},{2,12},{3,13} };unordered_map<int, int> map1(map);unordered_map<int, int>::iterator iter = hmap.begin();unordered_map<int, int>::iterator iter = hmap.end();bool isEmpty = map.empty();//判断是否为空int size = hmap.size();//哈希表的大小erase函数map.erase(iter_begin);  //删除开始位置的元素map.erase(iter_begin, iter_end); //删除开始位置和结束位置之间的元素map.erase(3); //删除key==3的键值对//clear()函数：清空哈希表中的元素map.clear();unordered_map<int, int>::iterator iter;iter = hmap.find(2); //返回key==2的迭代器，可以通过iter->second访问该key对应的元素if(iter != hmap.end())  cout << iter->second;int count = hmap.count(key);//统计哈希表键所对应的值的个数//哈希表的遍历for(auto iter=map.begin(); iter != map.end(); iter++){cout << "key: " <<  iter->first  << "value: " <<  iter->second <<endl;
}

小理解：

遇到不会的函数要积极动手查一查，你会发现有很多好用的函数

C语言是什么？不要联系我了，我现在只用C++

问：auto是啥？

答：auto是一种类型，像int，double，string，它能够根据后面是啥自动匹配对应的类型

通过下面的题目就会加深理解了^ ^

题目实战

1：存在重复元素

 暴力的方法很容易想到：两个for嵌套：时间复杂度是：O(N^2)

我这里给出的是小暴力的方法：时间复杂度是O(N*logN)

bool containsDuplicate(vector<int>& nums)
{sort(nums.begin(),nums.end());for(int i=1;i<nums.size();i++)if(nums[i]==nums[i-1])return true;retrun false;
}

哈希集合的方法：

思路解析：

遍历数组nums，将遍历到的元素插入hash集合中

如果哈希表的长度！=原数组的长度 -> 那么肯定有1个以上的重复元素插入到了哈希表

注意这只会导致元素作为索引对应的值增加，并不会使数组长度增加

画图理解：

原数组：

 理解：原数组的val作为了hashset的index，原数组val的频数作为了hashset的val

bool containsDuplicate(vector<int>& nums) {unordered_set<int>hash;for (int a : nums){hash.insert(a);}return hash.size() != nums.size();
}

---

 2：只出现一次的数字

 思路解析：

这道题用位运算也非常简单，具体的写法用异或，可以看看我的一篇文章《位运算的应用》

与上题同一种思路，如果没有出现过就插入，如果出现过就删除

class Solution {
public:int singleNumber(vector<int>& nums) {unordered_set<int> hash;for (auto& num : nums)//遍历数组{if (hash.count(num) > 0)//如果哈希表中有过一次元素{hash.erase(num);//删除该元素}else//如果哈希表之前没有过一次元素{hash.insert(num);//插入该元素}}//跳出循环后，哈希表中只剩下一个元素return *hash.begin();//哈希表中的开头地址解引用就是仅有的那个元素}
};

---

3：两个数组的交集

 思路解析：

开一个答案数组，用哈希表遍历存nums1的频数，遍历nums2，查找nums2是否有该元素，如果有，则尾插入答案数组，并在nums2中删除这个元素，防止重复出现

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {unordered_set<int> hashset;vector<int> result;for (auto val : nums1){hashset.insert(val);}for (auto val : nums2){if (hashset.count(val) > 0){result.push_back(val);hashset.erase(val);}}return result;}
};

4：快乐数

 思路解析：

设计一个函数cal 计算按照规律变化后的数字，并在哈希表中进行查询，如果哈希表中存在这个数，那么我们就可以知道，该数发生了重复，那么就直接返回false;反之如果这个数变了1，就跳出循环，返回true;

class Solution {
public:int cal(int n)//计算规则后的数
{int ans = 0;while (n){ans = ans + pow(n % 10, 2);n = n / 10;}return ans;
}bool isHappy(int n) {unordered_set<int> hashset;while (n != 1)//当不等于1的时候继续{n = cal(n);if (hashset.count(n))//如果计算后的数字与哈希存的数字重复{return false;//返回错误}hashset.insert(n);//如果没有则，插入到哈希中}return true;}
};

---

5：赎金信（字母异位词的开始）

 思路解析：

开一个26长度的数组去存储字母出现的频数，遍历第一个字符串，每遍历到一个字母就++

遍历第二个字符串，每遍历到一个字母就--，最后查找数组中是否有负数的情况，若有则说明第一个字符串不能由第二个字符串变形而来

 代码实现：

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

6：字母异位词分组

 思路解析：

与上题相同，判断是否位字母异位词，这道题的难点是，将单词分类，并归纳在一起

这里需要到了哈希表，而不是哈希集合，因为我们需要将单词排序后作为索引，而不是将数字作为索引，这是一种映射关系

这里就是哈希映射的的开始了^ ^

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string> >map;for (int i = 0; i < strs.size(); i++)//将取出的字符串排序后作为一类{string str = strs[i];sort(str.begin(), str.end());map[str].push_back(strs[i]);//将未排序的字符串插入至已排序好的那一类}vector<vector<string> >ans;for (auto it = map.begin(); it != map.end(); it++)//遍历尾插{ans.push_back(it->second);}return ans;}
};

补充：it->first是哈希表中的键，it->second是哈希表中的值

---

7：找到字符串中所有字母的异位词（滑动窗口+哈希）

 思路解析：

用scount数组存s字符串中的频数，用pcount数组存p字符串中的频数

以strlen(p)为长度作为滑窗，每次遍历判断长度为strlen(p)的scount是否与pcount相等

如果相等就插入答案数组，如果不相等就continue

class Solution {
public:vector<int> findAnagrams(string s, string p) {int slen = s.size();int plen = p.size();if (slen < plen){return vector<int>();}vector<int> ans;vector<int> sCount(26);vector<int> pCount(26);for (int i = 0; i < plen; i++){sCount[s[i] - 'a']++;pCount[p[i] - 'a']++;//用哈希表记录频数}if (sCount == pCount){ans.emplace_back(0);//如果这两个一开始频数相等，返回索引0}for (int i = 0; i < slen - plen; i++){sCount[s[i] - 'a']--;//滑动窗口从1开始滑！sCount[s[i + plen] - 'a']++;if (sCount == pCount)//判断此时窗口内的哈希是否与pcount相等{ans.emplace_back(i + 1);//若相等，尾插索引}}return ans;}
};

---

8：两数之和

 思路解析：

我们这里采用了哈希表的方法，遍历一遍数组，用哈希表查看是否存在{target-nums[i]}元素

如果存在则返回{target-nums[i]}，若不存在则将插入{键：nums[i]，值：i}

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int>hashmap;for (int i = 0; i < nums.size(); i++){if (hashmap.count(target - nums[i])){return { hashmap[target - nums[i]],i };}hashmap[nums[i]] = i;}return { -1,-1 };}
};

补充：这里的键和值的关系非常巧妙，注意体会^ ^

---

9：四数相加||

 思路解析：

注释已经很清楚了^ ^

这道题是升级版的两数之和

class Solution {
public:int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {unordered_map<int, int> map; //key:a+b的数值，value:a+b数值出现的次数// 遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中for (int a : A) {for (int b : B) {umap[a + b]++;}}int count = 0; // 统计a+b+c+d = 0 出现的次数// 在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就把map中key对应的value也就是出现次数统计出来。for (int c : C) {for (int d : D) {if (map.count(0 - (c + d))) {count += map[0 - (c + d)];}}}return count;}
};

补充：关于find和count，我更喜欢用count ^ ^ 二者都是查找哈希表

find是如果找不到就返回哈希表的尾地址

count是如果找到不到就返回0

---