昨天看了一下别的东西，导致昨天没有练习打卡，今天补上昨天的学习知识。
454.四数相加II
建议：本题是 使用map 巧妙解决的问题，好好体会一下 哈希法 如何提高程序执行效率，降低时间复杂度，当然使用哈希法 会提高空间复杂度，但一般来说我们都是舍空间 换时间， 工业开发也是这样。
题目链接：力扣
思路：给了我们四个数组，在四个数组之中分别找出一个元素，得到的结果为0，并且不用进行去重操作。可以先是遍历前面两个数组A+B，然后遍历后面的两个数组C+D。如果要是四个元素相加等于0，则可以得到结果元素。考虑到数组的下标比较大，考虑map和set，不仅要统计是否出现过，还要统计出现的次数，因此这里我们使用map解决这道题目。
map key：a+b value：3
这里的0-（c+d）=a+b则选择出来了。思路清晰了，则比较简单了。
为什么要分成两份，遍历前面两个的过程为n^2,然后后面也为n^2。如果要是分为1,3类型，则为n与n^3的情况。
这里使用undered_map对重复数据不敏感，并且效率高。见下面的测试代码
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
//首先，声明一个map，里面放置很多自己想要的数据，map的key就是相应的a+b的数值，value是a+b出现的次数
unordered_map<int,int> mymap;
for(int a:nums1)
{
for(int b:nums2)
{
mymap[a+b]++;//相当是value值想加
}
}
int count = 0;
for(int c:nums3)
{
for(int d:nums4)
{
if(mymap.find(0-(c+d))!=mymap.end())
{
count += mymap[(0-(c+d))];
}
}
}
return count;
}
};383. 赎金信
建议：本题和 242.有效的字母异位词是一个思路 ，算是拓展题.
题目链接:力扣
下面的这个代码是自己写的,比较容易理解.
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int record[26]={0};
if(ransomNote.size()>magazine.size())
{
return false;
}
for(int i=0;i<ransomNote.size();i++)
{
record[ransomNote[i]-'a']++;
}
for(int i=0;i<magazine.size();i++)
{
record[magazine[i]-'a']--;
}
for(int i=0;i<ransomNote.size();i++)
{
if(record[ransomNote[i]-'a']>0)
{
return false;
}
}
return true;
}
};15. 三数之和
建议：本题虽然和 两数之和 很像，也能用哈希法，但用哈希法会很麻烦，双指针法才是正解，可以先看视频理解一下 双指针法的思路，文章中讲解的，没问题 哈希法很麻烦。
题目链接:力扣
这个地方相较于两个的情况复杂一点点,a+b+c=0;这一个题要进行去重,因此是不能够使用hash法,首先进行排序,就是可以使用双指针方式进行求解.
这里的关键是要进行去重,因为结果集里面是不能够存在重复的东西.
步骤:①首先进行排序,然后遍历,如果大于0,直接进行一个return;
②去重操作,判断num[i]==num[i+1]与num[i]==num[i-1]的情况.注意结果集里面可以存在重复,因此遍历的时候使用num[i]==num[i-1]进行一个continue操作.
③注意left<right,不能够是=的情况.
④判断条件是否成立,成立的情况下,收割结果.
⑤防止{-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,1}的情况出现.
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) {
if (nums[i] > 0) {
return result;
}
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 {
result.push_back(vector<int>{nums[i], 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 result;
}
};18. 四数之和 ----没看懂,后面再看
建议： 要比较一下，本题和 454.四数相加II 的区别，为什么 454.四数相加II 会简单很多，这个想明白了，对本题理解就深刻了。 本题 思路整体和 三数之和一样的，都是双指针，但写的时候 有很多小细节，需要注意，建议先看视频。
题目链接:力扣
思路:在上面的那个题的基础上,增加了一个循环条件而已.四个数想加等于target的过程,存在一些细节(剪枝和去重操作)