目录
题目一：两数之和
题目二：判定是否互为字符重排
题目三：存在重复元素I
题目四：存在重复元素II
题目五：字母异位词分组
关于哈希表
哈希表就是存储数据的容器
哈希表的优势是：快速查找某个元素O(1)
所以当频繁查找某一个数时，就可以使用哈希表，这里提一点，在频繁查某个数时，也需要想到前面学过的二分算法，时间复杂度是O(logN)，虽然比哈希表慢一些，但是哈希表的空间复杂度高，而logN级别的时间复杂度也是非常快的，所以能使用二分还是建议使用二分
关于哈希表的使用：
①使用容器
②使用数组模拟哈希表，此时下标是K，内容是V
例如字符串的字符的操作，数据范围很小的时候，可以使用数组模拟
之所以使用数组模拟而不直接使用容器，是因为用数组模拟速度比较快，相比较而言，如果使用容器，还得new一个容器，查找时还需要调用接口，也有消耗
题目一：两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
需要注意，这道题要求一个元素不能重复在答案中出现
解法一：暴力解法
在我们前面所讲的暴力枚举方式，是固定一个数，再将这个数后面的所有数与该数的组合一一枚举出来，最终完成暴力枚举
这里采用相反的方向，先固定一个数，再与前面的数依次枚举，同样可以完成暴力枚举的操作
由于第一次使用这种查找前面数的暴力方式，所以写一下代码，便于理解，两层for循环，也是比较简单的：
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
for(int i = 0; i < nums.size(); i++)
{
for(int j = i - 1; j >= 0; j--)//从固定数的前面找符合要求的数
{
if(nums[i] + nums[j] == target) return {j, i};
}
}
//照顾编译器
return {0,0};
}
};解法二：哈希表优化
之所以在上面提到了第二种暴力枚举的思路，就是为了优化暴力枚举的方式，引入哈希表，具体说明如下：
数组是： [2,7,10,15]，目标是17
先固定一个数2，再找2之前的数，由于2之前没有数，所以往下遍历
接着固定7，再找7之前的数，不符合，继续向下遍历
这时遍历到10了，按照之前暴力枚举的思路，将固定的数与它之前的数依次相加，从而顺利找到目标值，但是可以引入优化的思路，此时就体现哈希的思想了：
既然此时固定的数是10，目标值是17，那么就不需要向前遍历，依次与10相加，判断是否等于目标值，直接将 目标值 - 固定的数 = 17 - 10 = 7，也就是在固定的数前面需要找一个数7，那么这时引入哈希表，在固定前面的数时都放入哈希表中，所以此时需要找7，就不需要遍历前面的数了，直接使用哈希表查找，哈希表查找的时间复杂度为O(1)，效率是非常高的，是典型的用空间换时间的算法，因为哈希表的空间复杂度是O(N)
这里说明一下，为什么需要引入第二种暴力枚举，来用哈希表进行优化呢，第一种暴力枚举的策略为什么不太好优化？
第一点：需要提前将元素放入哈希表
第一种暴力枚举的方式，是固定一个数，向后寻找，此时如果想用哈希表的策略，我们就需要提前将数组中的所有数放入哈希表中，才能够知道后面有没有数等于 (target - 该数)，比第二种方式差，第二种是边遍历边插入
第二点：很容易误判自己
由于刚开始将所有元素都放入了哈希表中，假设数组是[1,2,4,5]，目标值是8，当遍历到 4 这个数时，哈希表中已经有全部的元素在了，此时我们需要找的数是 8 - 4 = 4，很容易误判导致自己找到自己，因为需要找的是4，自己本身也是4，所以这里还需要特殊判断一下找到的数字是否是本身，而上面说的第二种方式，是从固定的数前面找，不会找到自己的，因为都是判断过了，才会插入到哈希表中
所以在做题时，哈希表中，第一个存的是数，第二个存的是该数的下标
代码如下：
class Solution
{
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int> hash;//<nums[i], i>
for(int i = 0; i < nums.size(); i++)
{
int ret = target - nums[i];//需要找的值
if(hash.count(ret))
{
return {hash[ret], i};
}
hash[nums[i]] = i;
}
//照顾编译器
return {0,0};
}
};题目二：判定是否互为字符重排
给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
示例 1：
输入:s1= "abc",s2= "bca" 输出: true
示例 2：
输入:s1= "abc",s2= "bad" 输出: false
这道题可以理解为：判断两个字符串重排列之后，所包含的字母是否相同，也就是判断两个字符串中包含的字母个数是否相同
所以很明显，就可以使用哈希表来统计出现的个数，使用容器unordered_map和数组模拟哈希表都能完成， 这里肯定是优先采用数组模拟的方法，因为数组的速度回快一些，并且容器的效率也不高，消耗也会比数组大一些，下面两种解法都列举：
解法一：使用unordered_map容器
先将第一个字符串的字符插入哈希表中，然后遍历另一个字符串，此时每遍历一个字符都判断是否在这个哈希表中，如果不在就return false，如果在value--，再在下面判断value是否为0，因为可能会出现多个相同字符，如果减到0了，就说明不对，return false即可
下面还可以优化一点，如果两个字符串长度都不同，那就不需要比较了，肯定是不同的
代码如下：
class Solution
{
public:
bool CheckPermutation(string s1, string s2)
{
if(s1.size() != s2.size()) return false;
unordered_map<char, int> hash(s1.size());
for(auto& it : s1) hash[it]++;//插入哈希表中
for(auto& it : s2)//遍历字符串2，与哈希表中元素比较
{
if(!hash.count(it)) return false;//如果没出现，返回false
if(hash[it] == 0) return false;//如果出现多次，返回false
--hash[it]; //每次出现value--
}
//走到这里还没有return，说明是相同的字符串
return true;
}
};解法二：数组模拟
只需要开大小为26的数组即可，因为题目中只会出现小写字母
同样使用上述的方法，只需要一个数组，将第一个字符串插入数组中，然后遍历第二个字符串，当出现相同字符时，该位置的数--，如果发现减到负数，就返回false
同样可以加上优化，如果两个字符串长度都不同，那就不需要比较了，肯定是不同的
代码如下：
class Solution
{
public:
bool CheckPermutation(string s1, string s2)
{
if(s1.size() != s2.size()) return false;
int hash[26] = {0};
for(auto& it : s1) hash[it - 'a']++;//插入数组对应位置中
for(auto& it : s2)//遍历字符串2，与数组中元素比较
{
//先--value，然后判断是否小于0
if(--hash[it - 'a'] < 0) return false;
}
//走到这里还没有return，说明是相同的字符串
return true;
}
};题目三：存在重复元素I
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入：nums = [1,2,3,1] 输出：true
示例 2：
输入：nums = [1,2,3,4] 输出：false
示例 3：
输入：nums = [1,1,1,3,3,4,3,2,4,2] 输出：true
这道题就是判断是否会出现重复元素，比较简单
可以使用上面的两数之和那道题的思路，当遍历到这个数时，找找这个数前面是否有数等于这个数，又因为并不需要关注下标，只需要关注是否出现，所以使用unordered_set即可
代码如下：
class Solution
{
public:
bool containsDuplicate(vector<int>& nums)
{
unordered_set<int> hash(nums.size());
for(int i = 0; i < nums.size(); i++)
{
if(hash.count(nums[i])) return true;
hash.insert(nums[i]);
}
return false;
}
};题目四：存在重复元素II
给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,1], k = 3 输出：true
示例 2：
输入：nums = [1,0,1,1], k = 1 输出：true
示例 3：
输入：nums = [1,2,3,1,2,3], k = 2 输出：false
这道题与上一道题解法基本相同，在上一题是否有重复元素的基础上，增加了条件，判断重复元素的下标之差是否小于等于K，所以这里的哈希表就需要统计下标了，所以就需要使用容器unordered_map了
同样，遍历到某个数时，先判断前面是否出现相同的数，如果出现，再下标之差是否小于等于K，如果都满足就return true，否则继续往后遍历，当遍历完还没有return，就说明没有符合条件的数，最后return false
代码如下：
class Solution
{
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_map<int, int> hash(nums.size());
for(int i = 0; i < nums.size(); i++)
{
//如果重复，则继续判断重复元素的下标是否满足条件
if(hash.count(nums[i]) && ((i - hash[nums[i]]) <= k))
return true;
hash[nums[i]] = i;
}
//走到这说明没有符合条件的数
return false;
}
};题目五：字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示：
1 <= strs.length <= 1040 <= strs[i].length <= 100strs[i]仅包含小写字母
此题是给出了字符串数组，vector<string>，每个元素存储的是一个字符串，最终将每一个相同字母组成的字符串放在一起，最终返回
这道题就是深度考验我们对于哈希表容器中类型的使用，我们可以想到一种非常巧妙的方法，首先需要判断是否是字母异位词，可以用上面的哈希表的方式，先将第一个字符串放入哈希表，再遍历第二个字符串，是否与哈希表中出现的一样，但是这种方式不利于更好的解决下面的问题，所以这道题的策略是：
将题目的每一个字符串都按照ASCLL码排序，创建一个unordered_map<string, vector<string>>，然后遍历题目给的字符串数组，如果出现相同的就插入到unordered_map的value中，如果出现不同的就新创建一个插入
再遍历这个哈希表，将相同位置的vector<string>都插入到一起，最终返回即可
代码如下：
class Solution
{
public:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
unordered_map<string, vector<string>> hash;
//把所有字母异位词分组
for(auto& it : strs)
{
//以排序后的tmp作为哈希表的Key，插入的it作为Value
string tmp = it;
sort(tmp.begin(), tmp.end());
hash[tmp].push_back(it);
}
//结果提取出来
vector<vector<string>> ret;
//表示将哈希表的元素都提取出来，first存在x里，second存在y里
for(auto& [x,y] : hash)
{
ret.push_back(y);
}
return ret;
}
};哈希表题目到此结束啦
