今天来讲一个可以让做题很舒服的专题哈希表哈希表是从哈希的思想发展来的可以分成两种哈希表unordered_set和unordered_map这两种数据结构底层都是用哈希表来进行封装的就像map和set底层是用红黑树来进行封装的之后一定会更新这部分相关的博客的简单来说哈希表查找元素的效率是O(1),可以很方便地查找当然我们的题目有的会使用数组来模拟哈希表因为用数组来就能够解决了1.两数之和题目链接1. 两数之和 - 力扣LeetCode这道题可以用暴力枚举来写好想也好做但时间复杂度比较高为On^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字母异位词相当于就是前面的字母重排因此我们只需要先将每一个字符进行排序再根据排序之后的结果按位置插入到哈希表中最后再从哈希表中提取出来就好了代码如下