哈希表理论基础

哈希表本质上统称为可以实现 迅速查找到一个集合中的指定元素 或 判断元素是否在集合中 的方法。

例如：

• 对于数组，有下标，迅速找到元素，O(1) 的时间复杂度。
• 对于 set，有元素，判断元素是否在集合中。
• 对于 map，有 key，迅速找到元素，O(1) 时间复杂度。

在 C++ 语言中，set 和 map 都分别提供了三种数据结构，每种数据结构的底层实现和用途都有所不同。简而言之：

• 如果你只需要判断元素是否出现过，可以使用 set。
• 如果你还想要元素出现次数，则可以使用数组或 map，因为后者都可以记录两个维度。

数组作为哈希表

有效的字母异位词：因为可能出现的字母数量有限，且需要记录字母出现次数，数组是更优的选择。
赎金信：一个字符串能否由另一个组成，只出现字母——暗示我们使用数组！

两者相同的地方：

• 前者为两个字符串能否互相由对方组成。
• 后者只要求一个字符串能否由另一个组成，是单向的！

set 作为哈希表

两个数组的交集：求交集是 set 的拿手好戏。求交集本质上是判断元素在集合中出现的次数是 0 还是 1。虽然数组也可以用 0 或 1 代表元素是否在集合中出现过，但数组适合元素个数有限的情况。这道题中的元素范围非常大，因此 set 更合适。

在 std::set、std::multiset、std::unordered_set 这三种中：

• 这道题不需要元素有顺序，也不要求重复，使用 unordered_set 就行。

在 快乐数 中，再次使用了 unordered_set 来判断一个数是否重复出现过。

map 作为哈希表

两数之和：首次出现 map 的身影。不仅要在数组中找出和为 target 的那两个整数，还需要返回它们的数组下标。因此需要记录整数及其下标，map 是最合适的哈希实现。

两数之和 中并不需要 key 有序，选择 std::unordered_map 效率更高！

四数相加 II：四个数组分别找出一个元素使 nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0。暴力情况是 4 层 for 循环（n^4 次方），但使用哈希来存储前两个数组的所有配对情况（key 为配对和，value 为该配对和出现的次数），随后枚举后两个数组，查找其互补数在哈希表中出现的次数。

对于 三数之和、四数之和，哈希法困难很多，使用双指针则简便许多。大致思路是：

• 如果固定一个数 a，问题就变成了在剩余元素中找到两个和为 target - a 的数，类似于两数之和的问题：“在一个数组中找到和为 val 的两个数字”。
• 区别在于两数之和要求返回下标，而这道题不需要，因此排序后使用首尾指针找剩余元素更方便，只需注意剪枝的写法即可。