哈希表题目技巧总结

哈希表介绍

哈希表是根据关键码值(key & value)而直接进行访问的数据结构。它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。

在C++SLT中，哈希表的容器是unordered_map，它有一个key值与一个value值，其中可以通过key值直接访问value值，而不需要借助value值的绝对地址，因此其特点之一就是直接访问，时间复杂度为 $O (1)$ 。同时，key值具有唯一性，不会存在重复的key值，且是无序的。

注：C++STL中，容器map实际上是红黑树，可以看成在哈希表的基础上增加了对key值的排序，因此其每次操作的复杂度都是 $O (l o g_{2} n)$ 。

用法举例

哈希表在题目中最主要的功能是快速访问，其次是去重等，具体用法如下所示：

快速统计字符串字符、数组元素、链表节点值、树/图节点值等出现的频次

可以将key值设置为要记录的元素，value值设置为其出现的频次，根据key值的无重复性和对value的直接访问，可以实现一次遍历快速统计频次。
快速访问之前记录过的元素

有时候需要快速访问之前记录的元素，我们就可以将其全部放入哈希表的key值中，则根据key值有无出现可以在 $O (1)$ 复杂度内快速查询。
去重，充当集合的功能

集合的特点是没有重复元素，在C++STL中可以用set或者unordered_set来当集合容器，如果集合的元素多了另一属性，则可以用unordered_map来代替，因为哈希表是二元数据结构，且同样具有去重的效果。
不使用unordered_map，直接用数组下标或者链表链接原地构造哈希表

有时候在可以使用哈希表的情况下，为了优化空间，降低空间复杂度，可以用数组的下标等具有地址指向效果的东西来充当哈希表，构造原地哈希。

经典题型

题目①最小覆盖子串

这道题主要是上述提到的哈希表的用法3，它通过哈希表构造了字符串的字符集，实现了快速访问。
题目②两数之和

这道题主要是上述提到的哈希表的用法2，快速访问之前遍历过的数组元素，以便快速找到与这个数相加匹配的另一个数出现的下标。
题目③数组中出现次数超过一半的数字

这道题主要是上述提到的哈希表的用法1，快速统计数组中各个数字出现的频率。
题目④字符串出现次数为topK问题

这道题主要是上述提到的哈希表的用法1，快速统计字符串数组中不同字符串出现的次数，可以直接对字符数组去重统计。
题目⑤数组中只出现一次的两个数字

这道题主要是上述提到的哈希表的用法1，快速统计数组中各个不同数字出现的次数，然后遍历哈希表找到需要的次数。
题目⑥缺失的第一个正整数

这道题常规方法是使用上述哈希表的用法1，统计数组各个正整数的频次，优化后的方法可以化为原地哈希，用数字与下标的关系当成地址索引。
题目⑦最长无重复子数组

这道题可以看成充当集合内的去重效果，使用的上述用法3.将滑动窗口内所有元素看成集合，保证集合内不重复，如果有重复则缩短窗口。