深度解析算法之哈希
57.两数之和
题目链接
给定一个整数数组 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]
这个代码是我之前的代码
class Solution {
public:
//思路：定义两个指针，i和j，i指向我们的数组第一个数，j指向我们数组的最后一个数
//如果我们的i和j下标对应的数字之和大于target的话，那么我们让j--，反之的话就让i++,直到找到这个数
vector<int> twoSum(vector<int>& nums, int target)
{
vector<int>temp(nums);//拷贝一个没有排序的nums赋值在tmp中
sort(nums.begin(),nums.end());//进行排序的操作，保证我们这边给到的数组是有序的数组
int n=nums.size();//将数组的数据个数表示出来
//可以先试用while循环，直到我们的两个下标找到了对应的数据
int i=0,j=n-1;
while(true)
{
if(nums[i]+nums[j]>target)
{
j--;
}
else if(nums[i]+nums[j]<target)
{
i++;
}
else//到这里就是相等了
{
break;
}
}
//出了循环，我们的两个指针就是我们要找的答案了
//新的问题：我们怎么将这两个数据进行返回呢？
vector<int> ret;//创建一个ret的容器
for(int k=0;k<n;k++)
{
if(temp[k]==nums[i]||temp[k]==nums[j])
{
ret.push_back(k);//将满足条件的k进行插入的操作，插入到我们返回结果的容器里面就行了
}
}
return ret;
}
};这里我们重新使用哈希表的知识进行问题的解决 在数组中找到两个值，大小为我们想要的target就行了 将这两个数进行返回操作
暴力解法：
- 先固定其中一个数
- 依次与该数之前的数相加 那么我们这里使用哈希表进行优化操作 我们一边向后面移动，我们一边将值丢到哈希表中去 在存的时候将nums[i]和这个数的下标i都丢进去
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 x=target-nums[i];//我们需要去哈希表中找到这个数
if(hash.count(x)) return {hash[x],i};//hash[x]里面存的就是我们要找的那个数的下标，i就是我们当前这个数的下标
//如果前面是没有或者是不存在x的话，那么我们将当前的数加到hash中去
hash[nums[i]]=i;//将当前的数和下标丢到hash中去
}
return {-1,-1};
}
};这个是我们使用hash的逻辑
58.判定是否互为字符重排
题目链接
给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
示例 1：
输入: s1 = “abc”, s2 = “bca”
输出: true
示例 2：
输入: s1 = “abc”, s2 = “bad”
输出: false
如果是重排的话，那么两个字符串中的每个字符对应的数量肯定是一样的
我们这里是使用数组模拟哈希表 使用两个哈希表，然后判断两个哈希表是否相等
优化：只使用一个哈希表 我们先遍历s1，将字幕出现的次数放进去 然后再遍历s2，将出现的字符都从哈希表中减去出现的次数 我们最后再判断哈希表中是否都为0，如果都为0的话，就说明这两个字符串是重排的，如果还有数据的话就说明这两个字符串有几个字符出现的次数是不相等的
如果两个字符串的长度不相等的话，那么直接返回false就行了
class Solution {
public:
bool CheckPermutation(string s1, string s2)
{
if(s1.size()!=s2.size()) return false;//长度不相等的话直接返回了
int hash[26]={0};
//先统计第一个字符串的信息
for(auto ch:s1)
hash[ch-'a']++;//将出现的字母的个数进行统计
//扫描第二个字符串，看看是否重排
for(auto ch:s2)
{
hash[ch-'a']--;//将hash中对应字母出现的次数减减
if(hash[ch-'a']<0) return false;//如果此时这个字母的次数小于0了，那么就说明字符出现次数是不匹配的
}
//出了循环的话，我们都没有返回，那么我们就说明两个字符串是重排的
return true;
}
};59.存在重复元素
题目链接给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
示例 1：
输入： nums = [1,2,3,1]
输出： true
解释：
元素 1 在下标 0 和 3 出现。
示例 2：
输入： nums = [1,2,3,4]
输出： false
解释：
所有元素都不同。
示例 3：
输入： nums = [1,1,1,3,3,4,3,2,4,2]
输出： true
class Solution {
public:
bool containsDuplicate(vector<int>& nums)
{
unordered_set<int>hash;
for(auto x:nums)
if(hash.count(x)) return true;//如果我们的哈希表中存在当前这个数，并且我们当前的数没有被记录，所以我们当前的这数出现了两次了
else hash.insert(x);//x没有出现过在哈希表中，那么我们将当前x插入到哈希表中就行了
return false;//到这里的话我们是循环结束了，循环结束了还是没有返回的话就说明这个数只出现了一次或者是没有出现的
}
};60.存在重复元素 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
利用hash表 hash<int,int>第一个int是nums[i]，第二个int是nums[i]的下标
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_map<int,int>hash;
for(int i=0;i<nums.size();i++)
{
if(hash.count(nums[i]))//如果当前这数在之前被记录在hash中了
{
if(i-hash[nums[i]]<=k) return true;//这个就是说明我们找到了符合条件的两个数
}
hash[nums[i]]=i;//如果没有被记录在hash中的话，我们将当前这个数存在hash中去
}
return false;
}
};61.字母异位词分组
题目链接 给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [[“bat”], [“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
输入: strs = [""]
输出: [[“”]]
示例 3:
输入: strs = ["a"]
输出: [[“a”]]
1.我们先判断两个字符串是否是字母异位词，我们可以通过排序解决
2.如何将字母异位词进行分组操作
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
unordered_map<string,vector<string>>hash;//第一个是字符串，第二个存的这个字符串的异位词
//1.将所有的字母异位词分组
for(auto&s:strs)
{
string tmp=s;
sort(tmp.begin(),tmp.end());//将这个字符串进行一个排序操作
hash[tmp].push_back(s);//在hash中进行对应字符串的统计并且存储异位词
}
//2.将结果提取出来
vector<vector<string>>ret;
for(auto&[x,y]:hash)//将hash中的元素提取出来，first存在x中，second存在y中
{
ret.push_back(y);//我们需要的是这个y就行了,我们将分类的结果存在ret中
}
return ret;
}
};腾讯云开发者
