什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。

242.有效的字母异位词

建议： 这道题目，大家可以感受到 数组 用来做哈希表 给我们带来的便利之处。

题目链接/文章讲解/视频讲解

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

思路

本质就是每个字母计数，用哈希表方便查找。

使用数组来做哈希的题目，是因为题目都限制了数值的大小。

时间复杂度O(n)
空间复杂度O(1)

注意

int hash[26] = {0};
初始化的时候注意加大括号。
英文字母有26个。

349. 两个数组的交集

建议：本题就开始考虑 什么时候用set 什么时候用数组，本题其实是使用set的好题，但是后来力扣改了题目描述和 测试用例，添加了 0 <= nums1[i], nums2[i] <= 1000 条件，所以使用数组也可以了，不过建议大家忽略这个条件。 尝试去使用set。

题目链接/文章讲解/视频讲解

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());for (int num : nums2) {if (nums_set.find(num) != nums_set.end()) {result_set.insert(num);}}return vector<int>(result_set.begin(), result_set.end());}
};

思路

使用数组来做哈希的题目，是因为题目都限制了数值的大小。

而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。

此时就要使用另一种结构体了，set ，关于set，C++ 给提供了如下三种可用的数据结构：

• std::set
• std::multiset
• std::unordered_set

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

时间复杂度O()
空间复杂度O()

注意

unordered_set<>牢记
初始化：
unordered_set nums_set(nums1.begin(), nums1.end())
查找：
nums_set.find(num) != nums_set.end() 找不到即返回 .end()

202. 快乐数

建议：这道题目也是set的应用，其实和上一题差不多，就是 套在快乐数一个壳子

题目链接/文章讲解/视频讲解

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;int sum = getSum(n);while (1) {if (sum == 1) return true;if (set.find(sum) != set.end()) return false;set.insert(sum);sum = getSum(sum);}}
};

思路

一开始没有想到要用哈希表，需要记住的是 题目中需要判断是否有重复出现 那就可以使用哈希表

时间复杂度O(log n)
空间复杂度O(log n)

注意

时间复杂度和空间复杂度计算比较复杂
复杂度计算

判断循环可以用哈希表

1. 两数之和

建议：本题虽然是 力扣第一题，但是还是挺难的，也是 代码随想录中 数组，set之后，使用map解决哈希问题的第一题。

题目链接/文章讲解/视频讲解

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 tmp = target - nums[i];auto iter = map.find(tmp);if (iter != map.end()) {return {iter->second, i};}else {map.insert(pair<int, int>(nums[i], i));}}return {};}
};

思路

哈希表，但不是set，而是要用map，因为需要保存值和下标，这样的一组键值对。

对于求和之类的题目，都是可以用目标和减去当前值，得到差，再去查找差。有一个查找的过程，可以用哈希表优化。

时间复杂度O(n)
空间复杂度O(n)

注意

map的设定：
unordered_map<int, int> map;

c++有自动的变量符号 auto
auto iter = map.find(tmp);

map可以用second取第二个值
iter->second

指纹锁大全