哈希表经典题目
数组作为哈希表
一些应用场景就是为数组量身定做的。
在有效的字母异位词中，我们提到了数组就是简单的哈希表，但是数组的大小是受限的！这道题目包含小写字母，那么使用数组来做哈希最合适不过。
在赎金信中同样要求只有小写字母，那么就给我们浓浓的暗示，用数组！本题和 有效的字母异位词 很像，有效的字母异位词 是求 字符串a 和 字符串b 是否可以相互组成，在 赎金信 中是求字符串a能否组成字符串b，而不用管 字符串b 能不能组成 字符串a。
上面两道题目用map确实可以，但使用map的空间消耗要比数组大一些，因为map要维护红黑树或者符号表，而且还要做哈希函数的运算。所以数组更加简单直接有效！
set作为哈希表
在两个数组的交集中我们给出了什么时候用数组就不行了，需要用set。这道题目没有限制数值的大小，就无法使用数组来做哈希表了。
主要因为如下两点：
- 数组的大小是有限的，受到系统栈空间（不是数据结构的栈）的限制。
- 如果数组空间够大，但哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。所以此时一样的做映射的话，就可以使用set了。
关于set，C++ 给提供了如下三种可用的数据结构：
- std::set
- std::multiset
- std::unordered_set
std::set 和 std::multiset 底层实现都是红黑树，std::unordered_set 的底层实现是哈希，使用 unordered_set 读写效率是最高的，本题并不需要对数据进行排序，而且还不要让数据重复，所以选择 unordered_set。
在快乐数中，我们再次使用了 unordered_set 来判断一个数是否重复出现过。
map作为哈希表
在两数之和中map正式登场。
来说一说：使用数组和set来做哈希法的局限。
- 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
- set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。
- map是一种<key, value>的结构，本题可以用key保存数值，用value在保存数值所在的下标。所以使用map最为合适。
C++提供如下三种map：
- std::map
- std::multimap
- std::unordered_map
std::unordered_map 底层实现为哈希，std::map 和std::multimap 的底层实现是红黑树。
同理，std::map 和 std::multimap 的 key 也是有序的，两数之和 中并不需要key有序，选择 std::unordered_map 效率更高！
在四数相加 II中我们提到了其实需要哈希的地方都能找到map的身影。
本题咋眼一看好像和 四数之和，三数之和 差不多，其实差很多！
关键差别是本题为四个独立的数组，只要找到 A[i] + B[j] + C[k] + D[l] = 0 就可以，不用考虑重复问题，而 四数之和，三数之和 是一个数组（集合）里找到和为0的组合，可就难很多了！
用哈希法解决了两数之和，很多同学会感觉用哈希法也可以解决 三数之和，四数之和。
其实是可以解决，但是非常麻烦，需要去重导致代码效率很低。
双指针
在三数之和中我给出了 双指针 解法，大家就可以体会到，使用哈希法还是比较麻烦的。
所以 四数之和，三数之和 都推荐使用双指针法！
