【哈希进阶】-创新互联
题目：454. 四数相加 II
题意：给了 4 个数组，查询 4 个数 之和等于0的四元组的个
思路1 ：暴力 四层 for 循环 —— O(
)
思路2 ：哈希法 —— O()
我们把前两个数组当成第一组，后两个数组当成第二组，遍历 第一组 ，将任意两个元素的和出现的次数存到map中；
遍历第二组，在第二组找有没有符合 s2 = (0 - （nums[i] + nums[j]) ) ，如果有 就将 count 加 s2 出现的次数，最后返回count 即可
class Solution {
public:
int fourSumCount(vector& nums1, vector& nums2, vector& nums3, vector& nums4) {
unordered_mapres;
int s1 = 0;
int count = 0;
for(int i = 0; i< nums1.size(); i++) {
for(int j = 0; j< nums2.size(); j++) {
s1 = nums1[i] + nums2[j];
res[s1]++;
}
}
int s2 = 0;
for (int i = 0; i< nums3.size(); i++) {
for (int j = 0; j< nums4.size(); j++) {
s2 = (0 - (nums3[i] + nums4[j]));
if(res.find(s2) != res.end()){
count += res[s2];
}
}
}
return count;
}
}; 1.为什么用哈希？
哈希是可以在最快时间查找一个数是否在集合中出现过
本题 我们 查找 s2 = (0 - （nums[i] + nums[j]) ) 是否在 集合中出现过
2.为什么用map哈希？
首先，因为本题数值范围不确定，用数组哈希映射浪费空间
其次，我们需要知道 数值 以及 数值出现的次数，这就需要 key value 结构，而set 不满足条件，因此，只能用map 做哈希，key 存放的是 第一组 遍历每一次的数值和， value 存的是出现的次数
3.最后是 count += 1 还是 count += res[s2]?
是 count += res[s2]， 我们是要加 这个值出现的次数，也就是value 值
题目：383. 赎金信
题意： 给两个字符串，判断 一个字符串是否可以由另一个字符串构成
思路1：暴力 —— O()
两层for循环遍历，有相同的字符，ransomNote 就删除掉对应的字符，最后判断 ransomNote字符串的长度，等于 0 说明 magazine 可以 构成 ransomNote ；
注意：要先循环 magazine字符串，第一次暴力写成先循环 ransomNote，没Ac，因为是在magazine 中找到能 构成 ransomNote 的字符
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
for (int i = 0; i< magazine.size(); i++) {
for(int j = 0; j< ransomNote.size(); j++) {
if (ransomNote[j] == magazine[i]) {
ransomNote.erase(ransomNote.begin()+j);
//erase函数 是删掉 括号范围内中间的数据
}
}
}
if(ransomNote.length() == 0) {
return true;
}
return false;
}
};思路2：哈希 —— O(n)
这道题和242.有效的字母异位词相似，这里我们需要假设两个字符串所有字母都是小写，然后就可以用数组来哈希，因为是判断后者是否可以构成前者，所以我们让后者（也就是magazine字符串）中出现的字母 次数 ++，而前者（也就是ransomNote 字符串）出现的字母 --，最后判断条件是res[i]< 0 ，表示 ransomNote 中有 magazine 没有的字母，返回false
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int res[26] = {0};
//这个条件第一次写没有加，但同样Ac了
if (ransomNote.size() >magazine.size()) {
return false;
}
for(int i = 0; i< magazine.size(); i++) {
res[magazine[i] - 'a']++;
}
for(int i = 0; i< ransomNote.size(); i++){
res[ransomNote[i] - 'a']--;
}
for (int i = 0; i< 26; i++) {
if(res[i]< 0) {
return false;
}
}
return true;
}
};题目：三数之和
题意：给定一个数组，在数组里面找到三个数，是他们的和等于0，返回三个数的数值，要去重
思路1：哈希（较麻烦，因为 去重细节不好处理）
两层for循环就可以确定 a 和b 的数值了，可以使用哈希法来确定 0-(a+b) 是否在 数组里出现过，但是我题目中说的不可以包含重复的三元组。
把符合条件的三元组放进vector中，然后再去重，这样是非常费时的，很容易超时
思路2：双指针——O()
这道题，双指针的思路很容易理解，难在去重；
双指针思路：因为题目中要求返回的是数值，而不是下标索引，所以我们可以对数组进行排序。排序后便于我们进行双指针的操作，初始 让 left 指针指向 i 的下一下位置 ，right 指针指向数组最后一个元素，开始进行条件判断 nums[i] + nums[left] + nums[right] >0,说明我们的范围大了，要缩小，因此 right--; 以此类推，nums[i] + nums[left] + nums[right]< 0, left++;
nums[i] + nums[left] + nums[right] = 0,说明找到符合条件的一组三元组，放到我们的答案数组中；找到后，就要让两个指针同时向内收缩，即 left++ ,right--;
关于去重：
a 的去重：a 如果重复了怎么办，a是nums里遍历的元素，那么应该直接跳过去
首先，因为数组是有序的 ，如果第一个数就大于0，则直接返回答案数组；
然后，nums[i] == nums [i - 1] 和 nums[i] == nums[i + 1] 这两种写法是有区别，nums[i] == nums [i - 1]是判断当前元素和前一个元素是否相等，符合a的去重； nums[i] == nums[i + 1]是判断当前元素和后一个元素是否相等，而我们后一个元素是nums[left]，即如果这样写，我们就是在三元组内部去重，不符合题意，题目只说要不重复的三元组，但三元组内部的元素可以重复；可以 以 {-1，-1，2}
b，c的去重：去重条件写在哪里？ 要写在收获一组答案后再去重。
去重b: right >left && nums[left] == nums[left + 1]
去重c ： right >left && nums[right] == nums[right - 1]
例如 数据 {-1，0，0，0，1，1，1} 可以得到一组答案 {-1，0，1}，此时left++, right--;此时得到的答案{-1，0，1} 因此要对b,c去重
class Solution {
public:
vector>threeSum(vector& nums) {
vector>res;
sort(nums.begin(),nums.end());
for(int i = 0; i< nums.size(); i++){
if(nums[0] >0) {
return res;
}
if(i >0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = nums.size()-1;
while(right >left) {
if(nums[i] + nums[left] + nums[right] >0) {
right--;
} else if(nums[i] + nums[left] + nums[right]< 0) {
left++;
} else {
res.push_back({nums[i], nums[left],nums[right]});
while(right >left && nums[right] == nums[right -1]) right--;
while(right >left && nums[left] == nums[left+1]) left++;
left++;
right--;
}
}
}
return res;
}
}; 题目：四数之和
题意：给定一个数组，求出数组中四数相加等于 target 的四元组，要去重
思路：双指针——O()
这道题和三数之和思路一样，只不过多了一层for循环，去重操作也是一样的，不过注意一下b的去重， 不是j >0 而是 j >i + 1;另外在标答中还有剪枝的操作，在这里并没有写出；另外双指针里面判断四个数相加时要转换成long 否则会溢出
class Solution {
public:
vector>fourSum(vector& nums, int target) {
vector>res;
sort(nums.begin(), nums.end());
for(int i = 0; i< nums.size(); i++) {
if(i >0 && nums[i] == nums[i - 1]) continue;
for(int j = i + 1; j< nums.size(); j++) {
if (j >i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = nums.size() - 1;
while(left< right) {
if((long)nums[i] + nums[j] + nums[left] + nums[right]< target) left++;
else if((long)nums[i] + nums[j] + nums[left] + nums[right] >target) right--;
else{
res.push_back({nums[i], nums[j], nums[left], nums[right]});
while (right >left && nums[right] == nums[right - 1]) right--;
while(right >left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
}
return res;
}
}; 剪枝操作：
class Solution {
public:
vector>fourSum(vector& nums, int target) {
vector>res;
sort(nums.begin(), nums.end());
for(int i = 0; i< nums.size(); i++) {
//剪枝 注意是正数的时候，两个正数相加越来越大，而两个负数相加则越来越小
if(nums[i] >0 && target >0 && nums[i] >target) break;
//去重
if(i >0 && nums[i] == nums[i - 1]) continue;
for(int j = i + 1; j< nums.size(); j++) {
//剪枝
if(nums[i] + nums[j] >0 && nums[i] + nums[j] >target) break;
//去重
if (j >i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = nums.size() - 1;
while(left< right) {
if((long)nums[i] + nums[j] + nums[left] + nums[right]< target) left++;
else if((long)nums[i] + nums[j] + nums[left] + nums[right] >target) right--;
else{
res.push_back({nums[i], nums[j], nums[left], nums[right]});
//去重
while (right >left && nums[right] == nums[right - 1]) right--;
while(right >left && nums[left] == nums[left + 1]) left++;
right--;
left++;
}
}
}
}
return res;
}
}; 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧
本文名称：【哈希进阶】-创新互联
文章来源：http://mswzjz.cn/article/jgdpi.html