算法学习：
https://blog.csdn.net/2301_80220607/category_12922080.html?spm=1001.2014.3001.5482
前言：
在之前学习数据结构时我们就学习了哈希表的使用方法，这里我们主要是针对哈希表的做题方法进行讲解，都是leetcode上的经典题，各位可以自己做一遍再来看一下，主要抽取了几个经典的题
1. 哈希表的基础知识1.1 哈希表是什么简单点来说哈希表就是一个存储数据的容器，但是能够对出现的数据进行标记
1.2 哈希表的作用能够实现快速查找指定的数据，时间复杂度往往为O(1)
1.3 什么时候用哈希表频繁的查找数据时
1.4 哈希表的应用场景1. 直接使用哈希表这个数据类型
2. 在合适的场景使用数组来模拟哈希表
解释:
2、3:当我们需要频繁查找数据的时候我们就可以想到要用哈希表，哈希表的时间复杂度为o(1)，空间复杂度为o(n)同时也要考虑是否可以用二分，二分时间复杂度为o(logn)，也非常快，而且二分没有时间开销
4:除了之间使用函数提供给我们的哈希表外，我们也可以用数组模拟创建一个简易的哈希表，但这种只适用于元素少的情况，比如让我们统计字符串中各字符出现次数，我们就可以用数组 int hash[26]模拟一下
2. 哈希表经典例题2.1 两数之和1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
代码语言：javascript代码运行次数：0运行复制输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。示例 2：
代码语言：javascript代码运行次数：0运行复制输入：nums = [3,2,4], target = 6
输出：[1,2]示例 3：
代码语言：javascript代码运行次数：0运行复制输入：nums = [3,3], target = 6
输出：[0,1]提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109只会存在一个有效答案算法原理：
解法一：暴力枚举
在这个暴力枚举中我们来考虑一种新的枚举思路
比如本题，按照之前的枚举策略，我们是要让当前位置(cur)与后面位置的数字依次相加，然后看是否有满足条件的数字
现在我们来看一种新的枚举思路，就是让所有位置的数字，与它前面位置的数字相加，然后判断是否有满足条件的两个数字这样的思路也能保证让所有的数两两相加，而且在处理一些细节上更有优势，尤其是本题，下面我们结合本题来感受一下
比如上面我们提到的这个队列，按照原来的思路，我们先来找一下2后面是否有合适的数字，使得2与其相加等于target，为了减小时间复杂度我们这里要用哈希表的方法，哈希表中存的值是数组中元素和对应的下标
比如这样一个数组和target值，如果我们按照原策略先将所有数字和对应下标放入哈希表中的话因为有两个3，在第一个3及它对应的下标放入哈希表中后，当放第二个3及它对应的下标时，就会把前一个存的3的下标给覆盖掉，所以我们还需要额外的操作对重复的数字的多个下标进行保存
但是如果我们采取的策略二，我们创建哈希表的时机就会发生一些变化，比如我们现在位置在2，我们是要从前面的位置找合适的数，前面没有数，所以哈希表中自然也没有，然后我们可以将2的值及它的下标放入哈希表中，同时让cur++，这样做的优化点是什么呢?
此时假如我们再遇到上面的情况(两个3)，我们在第一个3时査找它前面是否有合适的数(前面的数己经放入哈希表了)时，会发现没有，然后我们把它放入哈希表中，然后到第二个3，我们发现哈希表中hash[target-3]存有一个下标，我们就找到满足条件的下标了
假如我们现在的target不是6，而是14，那我们在经过第二个3后，虽然会把哈希表中3对应的下标替换掉，但是仍不影响最终结果
思考一下:其实第二种策略比第一种策略的优化之处就是，策略二在替换一个数的坐标之前，是事先知道这个数字两两相加不满足条件的，所以保留一个与其它数字相加即可，而第一个数字则是在没考虑这种情况之前就只把重复数字只留下一个
代码实现：
代码语言：javascript代码运行次数：0运行复制class Solution {
public:
vector
unordered_map
for(int i=0;i { if(hash.count(target-nums[i])) return {hash[target-nums[i]],i}; hash[nums[i]]=i; } return {-1,-1}; } };2.2 存在重复元素||219. 存在重复元素 II 给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。 示例 1： 代码语言：javascript代码运行次数：0运行复制输入：nums = [1,2,3,1], k = 3 输出：true示例 2： 代码语言：javascript代码运行次数：0运行复制输入：nums = [1,0,1,1], k = 1 输出：true示例 3： 代码语言：javascript代码运行次数：0运行复制输入：nums = [1,2,3,1,2,3], k = 2 输出：false提示： 1 <= nums.length <= 105-109 <= nums[i] <= 1090 <= k <= 105这道题就可以用上面的思路来解，挺简单的，可以练练手 代码实现： 代码语言：javascript代码运行次数：0运行复制class Solution { public: bool containsNearbyDuplicate(vector unordered_map for(int i=0;i { if(hash.count(nums[i])&&i-hash[nums[i]]<=k) return true; hash[nums[i]]=i; } return false; } };2.3 字母异位词分组49. 字母异位词分组 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 代码语言：javascript代码运行次数：0运行复制输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 输出: [["bat"],["nat","tan"],["ate","eat","tea"]]示例 2: 代码语言：javascript代码运行次数：0运行复制输入: strs = [""] 输出: [[""]]示例 3: 代码语言：javascript代码运行次数：0运行复制输入: strs = ["a"] 输出: [["a"]]提示： 1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i] 仅包含小写字母算法原理： 解释: 这道题就很考验我们对哈希表的使用，我们在这里创建的哈希表类型是一个 代码实现： 代码语言：javascript代码运行次数：0运行复制class Solution { public: vector unordered_map for(int i=0;i { string tmp=strs[i]; sort(strs[i].begin(),strs[i].end()); hash[strs[i]].push_back(tmp); } vector for(auto& [x,y]:hash) ret.push_back(y); return ret; } };3. 总结 以上就是几个关于哈希表的经典例题，都不算难，哈希表在算法题里出现的比例还是非常高的，一般都是作为一种数据类型存在的，掌握还是很有必要的 本篇笔记：