（给算法爱好者加星标，修炼编程内功）

来源：代码随想录 （本文来自作者投稿）

如果对哈希表还不了解的话，可以先看这篇 关于哈希表，你该了解这些！

接下来我们要明确 哈希法可以用来解决什么问题， 「当我们需要判断一个元素是否出现过的时候，就要考虑哈希表。」

哈希法通常使用如下三种数据结构 :

• 数组

• set

• map

接下来我们分别看一下三个容器在哈希法中的应用。

数组在哈希法中的应用

**
**

leetcode 383. 赎金信

这道题题意很清晰，就是用判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成，但是这里需要注意两点 1。

• 第一点“为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思” 这里说明杂志里面的字母不可重复使用。

• 第二点 “你可以假设两个字符串均只含有小写字母。” 说明只有小写字母，这一点很重要。

因为题目只有小写字母，那我们可以采用空间换取时间的哈希策略， 用一个长度为 26 的数组还记录 magazine 里字母出现的次数，然后再用 ransomNote 去验证这个数组是否包含了 ransomNote 所需要的所有字母。

题解：https://github.com/youngyangyang04/leetcode/blob/master/problems/0383. 赎金信 .md

leetcode 575. 分糖果

糖果的种类是可妹妹先来，所以思路先求出一共有多少种类型的糖果。

需要注意：数组中数字的大小也就是糖果的种类取值范围在 [负十万和 正十万之间]， 依然可以定义一个数组，通过哈希法求出有多少类型的糖果。

那么糖果种类可以是负数 怎么办呢，可以把 定一个 20 万大小的数组 ，就可以把糖果的全部类型映射到数组的下表了。

通过哈希法，可以求出了糖果的类型数量，如果糖果种类大于糖果总数的一半了，返回 糖果数量的一半就好，因为妹妹已经得到种类最多的糖果了，否则，就是返回 糖果的种类。

题解：https://github.com/youngyangyang04/leetcode/blob/master/problems/0575. 分糖果 .md

set 在哈希法中的应用

**
**

leetcode 349. 两个数组的交集

这道题目，主要要学会使用一种哈希数据结构，unordered_set，这个数据结构可以解决很多类似的问题。

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

这道题用暴力的解法时间复杂度是 O(n^2)，这种解法面试官一定不会满意，那我们看看使用哈希法进一步优化。

那么可以发现，貌似用数组做哈希表可以解决这道题目，把 nums1 的元素，映射到哈希数组的下表上，然后在遍历 nums2 的时候，判断是否出现过就可以了。

但是要注意，使用数据来做哈希的题目，都限制了数值的大小，例如只有小写字母，或者数值大小在 [0- 10000] 之内等等。而这道题目没有限制数值的大小，就无法使用数组来做哈希表了。

例如说：如果我的输入样例是这样的， 难道要定义一个 2 亿大小的数组来做哈希表么， 不同的语言对数组定义的大小都是有限制的， 即使有的语言可以定义这么大的数组，那也是对内存空间造成了非常大的浪费。

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

• std::set

• std::multiset

• std::unordered_set

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

题解：https://github.com/youngyangyang04/leetcode/blob/master/problems/0349. 两个数组的交集 .md

leetcode 202. 快乐数

这道题目重点是，题目中说了会 「无限循环」， 那么也就是说 求和的过程中，sum 会重复出现，这对我们解题很重要，这样我们就可以使用哈希法，来判断这个 sum 是否重复出现，如果重复了就是 return false， 否则一直找到 sum 为 1 为止。

还有就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。

题解：https://github.com/youngyangyang04/leetcode/blob/master/problems/0202. 快乐数 .md

map 在哈希法中的应用

**
**

leetcode 1. 两数之和

很明显暴力的解法是两层 for 循环查找，时间复杂度是 O(n^2) 。我们来看一下使用数组和 set 来做哈希法的局限。

• 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。

• set 是一个集合，里面放的元素只能是一个 key，而两数之和这道题目，不仅要判断 y 是否存在而且还要记录 y 的下表位置，因为我们要返回 x 和 y 的下表。所以 set 也不能用。

此时我们就要选择另一种数据结构 map ，map 是一种 key value 的存储结构，我们可以用 key 保存数值，用 value 在保存数值所在的下表。这道题目是 map 在哈希法中的经典应用。

题解：https://github.com/youngyangyang04/leetcode/blob/master/problems/0001. 两数之和 .md

leetcode 454. 四数相加 II

本题使用哈希表映射的方法。

那么为什么 18. 四数之和，0015. 三数之和不适用哈希表映射的方法呢，感觉上 这道题目都是四个数之和都可以用哈希，三数之和怎么就用不了哈希呢。

因为题目 15. 三数之和和 18. 四数之和，使用哈希的方法在不超时的情况下做到对结果去重很困难。

而这道题目 相当于说 不用考虑重复元素，是四个独立的数组，所以相对于题目 18. 四数之和，0015. 三数之和，还是简单了不少。

题解：https://github.com/youngyangyang04/leetcode/blob/master/problems/0454. 四数相加 II.md

三数之和 & 四数之和

三数之和 四数之和的问题，用哈希法也可以解决，但是最好使用双指针法，因为使用哈希法的话去重逻辑有很多细节需要注意，很难快速写出没有 bug 的代码。

所以几数之和的问题，我将单独写一篇文章来介绍。

• 题解：https://github.com/youngyangyang04/leetcode/blob/master/problems/0015. 三数之和 .md

• 题解：https://github.com/youngyangyang04/leetcode/blob/master/problems/0018. 四数之和 .md

**

**

总结

「哈希法的本质是空间换时间，通过数组，set 和 map 将数据已经预处理，从而通过 O(1) 的时间复杂度快速判断出元素是否出现某个集合中。」

数组的限制是数组的大小，当我们的哈希值超过了数组大小的时候，就无法映射到数据下表上。

进而采用 set，set 的限制是只能存放单一 key，不能记录更多的数据。

进而考虑 map，map 通过 `` 的存储结构，允许我们更加灵活的存储哈希值和对应的数值。

以上六道题目都非常具有代表性，大家可以按循序做一下，相信会对哈希法有所感悟。

来源链接：mp.weixin.qq.com
来源：算法爱好者