454.四数相加II
题目链接：454.四数相加II
文档讲解：代码随想录
状态：有思路但是不太清晰，看了题解
思路
关键点：解为个数，而不是下标或元素值->问题转变为，有几个->有没有、有几个 是一个哈希表问题。
关键点：四个独立数组，没用去重操作，使用for循环遍历即可。
不但要所有情况的加和，还需要加和的个数（统计结果），使用map。
题解
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> umap;
for(auto i:nums1)
{
for(auto j:nums2)
{
umap[i+j]++;
}
}
int result = 0;
for(auto i:nums3)
{
for(auto j:nums4)
{
result += umap[-i-j];
}
}
return result;
}
};
383. 赎金信
思路
典型的字母<->数量，的数组哈希表问题
重点学习优化点，两个相同数组比较各个位大小时，可以分别遍历：先 arry[i]++再 arry[i]++，节省空间
题解
class Solution {//第一次飞速一遍过！！！
public:
bool canConstruct(string ransomNote, string magazine) {
int arry[26] = {0};
for(auto i:magazine)
{
arry[i-'a']++;
}
for(auto i:ransomNote)
{
arry[i-'a']--;
}
for(int i = 0;i<26;i++)
{
if(arry[i]<0)return false;
}
return true;
}
};
第15题. 三数之和
题目链接：第15题. 三数之和
文档讲解：代码随想录
状态：不会，理解后AC
思路
我的思路：两个for循环加和，使用map保存和与下标（二元组），再遍历数组查找map，最后去重，太麻烦。
本题的关键在于去重操作，三元组不可重复的意义：<-1，0，1>与<0，1，-1>是重复的；<0，0，0>不算哦。
想一下去重的情况：例如一堆数组里有两组下标不同的<1，-1，0>分布无序，怎么去重的？哈希表？一想情况就很复杂，加和时：下标与各自值均要去重，再次遍历数组时还需要去重，细节太多。
再想想如何去重：只能是把重复的跳过去->数组必须得有序->单调性->双指针，大体思路有了。
额外掌握：给vector排序的方法、
算法过程：
去重细节如下图
题解
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());//给vector排序的方法你要知道
vector<vector<int>> result;
for(int i = 0;i<nums.size()-2;i++)
{
//可添加优化项目，什么情况不用遍历直接返回
//****
//根据图解去重
if(i>0 && nums[i] == nums[i-1])continue;//情况1去重
int left = i+1, right = nums.size()-1;
while(left<right)
{
if(nums[i]+nums[left]+nums[right]<0)left++;
else if(nums[i]+nums[left]+nums[right]>0)right--;
else
{
result.push_back(vector<int>{nums[i],nums[left],nums[right]});
left++;
right--;
while (right > left && nums[right] == nums[right + 1]) right--;//情况三去重
while (right > left && nums[left] == nums[left - 1]) left++;//情况二去重
}
}
}
return result;
}
};
18.四数之和
思路
有端联想三数之和，指针和去重情况一想便知
记得要先排序
注意本题出现了nums[i]+nums[j]+nums[left]+nums[right]值越界情况，学习如何强制类型转换，注意括号在哪！
题解
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(),nums.end());
vector<vector<int>> result;
if(nums.size()<4)return result;
for(int i = 0;i<nums.size()-3;i++)
{
if(i>0 && nums[i] == nums[i-1])continue;
for(int j = i+1;j<nums.size()-2;j++)
{
if(j>i+1 && nums[j] == nums[j-1])continue;
int left = j+1, right = nums.size()-1;
while(left<right)
{
if((long)nums[i]+nums[j]+nums[left]+nums[right]>target)right--;
else if((long)nums[i]+nums[j]+nums[left]+nums[right]<target)left++;
else
{
result.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
left++;
right--;
while(left<right && nums[left]==nums[left-1])left++;
while(left<right && nums[right]==nums[right+1])right--;
}
}
}
}
return result;
}
};
哈希表总结
一般来说哈希表都是用来快速判断一个元素是否出现集合里。
对于哈希表，要知道哈希函数和哈希碰撞在哈希表中的作用。
哈希函数是把传入的key映射到符号表的索引上、哈希碰撞处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。
最常见的三种哈希结构：
- 数组
- set（集合）
- map（映射）
在C++语言中，set 和 map 都分别提供了三种数据结构，每种数据结构的底层实现和用途都有所不同，例如什么时候用std::set，什么时候用std::multiset，什么时候用std::unordered_set，都是很有考究的。只有对这些数据结构的底层实现很熟悉，才能灵活使用，否则很容易写出效率低下的程序。
最后注意分辨题目所需的哪种容器为最优解。