企业官网建设流程全解析

今天来讲一个可以让做题很舒服的专题，哈希表，哈希表是从哈希的思想发展来的，可以分成两种哈希表unordered_set和unordered_map，这两种数据结构底层都是用哈希表来进行封装的，就像map和set底层是用红黑树来进行封装的，之后一定会更新这部分相关的博客的

简单来说，哈希表查找元素的效率是O(1),可以很方便地查找，当然，我们的题目有的会使用数组来模拟哈希表，因为用数组来就能够解决了

1.两数之和

题目链接：1. 两数之和 - 力扣（LeetCode）

这道题可以用暴力枚举来写，好想也好做，但时间复杂度比较高，为O（n^2），由于题目给的数组是有序的，暴力枚举的方法就是固定一边，开始枚举符合条件的两个数

代码如下：

当然，还有更快的方法，那就是用哈希表来解决

我们可以设置一个哈希表，从前往后来遍历数组

举个例子，当遍历到nums[i]这个元素时，因为我们要求的两数之和为target，因此我们只需要到哈希表里面找一下有没有值为target-nums[i]的元素就可以了，检查的方法也很简单，当我们遍历完一个数后，如果hash[nums[i]]==0,我们让该值在哈希表中对应的数值++就好了

还有一个需要注意的点，因为题目要求不能有重复的元素（注意是元素不能重复，值是可以重复的），所以我们在找值的时候还需要额外检查一下

具体代码如下：

可以来对比一下

这两种方法的效率是差很多的

2.判定是否互为字符重排

题目链接：面试题 01.02. 判定是否互为字符重排 - 力扣（LeetCode）

这道题还是比较简单的

第一个解法是先将两个字符串进行排序，然后一一对比对应元素是否相等就可以了

代码如下：

第二个解法就是利用哈希表，当然，这里没必要用到哈希表，因为题目规定了，字符串里面只可能有小写字母，所以我们可以创建大小为26的数组来模拟哈希表，通过字符的ascii码来映射对应的位置

具体代码如下：

两种解法前面都有判断大小，因为如果大小都不相等，那就一定不是字符重排了

3.存在重复元素

题目链接：217. 存在重复元素 - 力扣（LeetCode）

这道题如果不用哈希表，可能就很难，但用哈希表，就很舒服，我们可以直接统计所有元素出现的次数，然后直接遍历哈希表查找就好了

代码如下：

4.存在重复元素II

题目来源：219. 存在重复元素 II - 力扣（LeetCode）

这道题在上一道题的基础上，额外增加了一个条件限制，要求两个相同元素的下标差不能超过k

这道题同样可以用哈希表来解决，只不过哈希表中存放的数据从元素个数变为了下标，方便我们进行判断

但是这样操作会有一个问题，每次判断完放入新下标时，可能会覆盖掉前面的下标

事实上，并不会有影响

假如当前下标与哈希表中已存在的下标都不满足下标之差小于等于k，那么继续往后遍历出来的下标也肯定不满足这个要求了

所以可以大大方方覆盖掉

代码如下：

5.字母异位词分组

题目链接：49. 字母异位词分组 - 力扣（LeetCode）

字母异位词相当于就是前面的字母重排，因此我们只需要先将每一个字符进行排序，再根据排序之后的结果按位置插入到哈希表中，最后再从哈希表中提取出来就好了

代码如下：