代码随想录一刷记录Day6——leetcode454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和
前言
之前就有刷代码随想录，但奈何总是三天打鱼两天晒网，而且刷的也很囫囵吞枣，于是乎决定参加代码随想录训练营，准备精刷一遍，希望自己能坚持下去，结营后自己的算法水平能更上一个level，冲ing！
leetcode454.四数相加II
题目链接leetcode454.四数相加II
思路
因为是在四个数组中找和为0的元素，即判断某元素在集合中是否出现首先就要想到哈希表。因为不需要去重，且需要知道元素是否出现以及出现的次数，所以unordered_map是最好的选择。四个数组中，前两个看作一个大数组，后两个看作一个大数组。
具体步骤：
1、首先定义 一个unordered_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
2、遍历nums1和nums2数组，统计两个数组元素之和，和出现的次数，放到map中。
3、定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
4、再遍历nums3和nums4数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
5、最后返回统计值 count 就可以
代码
classSolution{public:intfourSumCount(vector<int>&nums1,vector<int>&nums2,vector<int>&nums3,vector<int>&nums4){unordered_map<int,int>umap;//key:a+b的数值，value:a+b数值出现的次数//遍历nums1和nums2数组，统计两个数组元素之和，和出现的次数，放到map中for(inta:nums1){for(intb:nums2){umap[a+b]++;}}intcount=0;//统计a+b+c+d = 0 出现的次数//再遍历nums3和nums4数组，找到如果0-(c+d)在map中出现过的话，就把map中key对应的value也就是出现次数统计出来for(intc:nums3){for(intd:nums4){if(umap.find(0-(c+d))!=umap.end()){count+=umap[0-(c+d)];}}}returncount;}};leetcode383. 赎金信
题目链接leetcode383. 赎金信
思路
之间做的leetcode242.有效的字母异位词相当于求 字符串a 和 字符串b 是否可以相互组成 ，而这道题目是求 字符串a能否组成字符串b，而不用管字符串b 能不能组成字符串a。两道题整体思路是一样的，都是使用数组作哈希表，定义一个record数组，只是最后判断record的逻辑略有不同。
本题中，magazine中出现了的字符就++，ransomNote出现了字符就–，然后判断record中是否由<0的记录，如果有就说明ransomNote里出现的字符，magazine没有。
代码
classSolution{public:boolcanConstruct(string ransomNote,string magazine){intrecord[26]={0};if(ransomNote.size()>magazine.size()){returnfalse;}for(inti=0;i<magazine.size();i++){//通过record数据记录magazine里各个字符出现次数record[magazine[i]-'a']++;}for(intj=0;j<ransomNote.size();j++){//遍历ransomNote，在record里对应的字符个数做--操作record[ransomNote[j]-'a']--;//如果小于零，说明ransomNote里出现的字符，magazine没有if(record[ransomNote[j]-'a']<0){returnfalse;}}returntrue;}};leetcode15. 三数之和
题目链接leetcode15. 三数之和
思路
本体需要去重，如果仍然像之前做的两数之和那道题那样使用哈希法的话，去重会非常麻烦。本体更适合使用双指针思路。
- 核心1——双指针的使用
初始时，i从数组起始位置开始遍历充当a，left为i的下一个位置作为b，right为最后一个位置作为c；寻找满足a+b+c等于0的三个数。
循环前先对数组排序，这样a+b+c>0就让right–，a+b+c<0，就让left++。这是本体应用双指针的整体思路。 - 核心2——去重的方法
a的去重：
nums[i] == nums[i + 1] ，这种写法，三元组中出现重复元素的情况直接pass掉了。 例如{-1, -1 ,2} 这组数据，当遍历到第一个-1 的时候，判断下一个也是-1，那这组数据就pass了。我们要做的是 不能有重复的三元组，但三元组内的元素是可以重复的！
nums[i] == nums[i - 1]，这种写法正确的。当前使用 nums[i]时，需判断前一位是不是一样的元素，在看 {-1, -1 ,2} 这组数据，当遍历到 第一个 -1 的时候，只要前一位没有-1，那么 {-1, -1 ,2} 这组数据一样可以收录到 结果集里
b与c的去重：
while(right > left && nums[right] == nums[right-1]) right–;
while(right > left && nums[left] == nums[left+1]) left++;
注意放的位置，应保证至少收集了一次结果，在进行去重，如果先执行去重，最终将一组结果都收集不到，例如{0,-1,-1,-1,1,1,1}
代码
classSolution{public:vector<vector<int>>threeSum(vector<int>&nums){vector<vector<int>>result;sort(nums.begin(),nums.end());//找出 a+b+c=0//a=nums[i], b=nums[left], c=nums[right]//固定第一个数for(inti=0;i<nums.size();i++){//排序之后如果第一个元素就已经大于0，那么无论怎么组合都凑不成if(nums[i]>0){returnresult;}//去重a方法if(i>0&&nums[i]==nums[i-1]){continue;}intleft=i+1;intright=nums.size()-1;while(left<right){if(nums[i]+nums[left]+nums[right]>0)right--;elseif(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++;}}}returnresult;}};leetcode18. 四数之和
题目链接leetcode18. 四数之和
思路
本题和三数之和的整体思路是一致的，只是在三数之和的基础上再套一层for循环。每一层分别做剪枝和去重操作。
注意的是：本体target不再是0，所以一级去重的时候不能仅仅用 if（nums[k] > target）break，因为可能是负数，负数加负数会更小。
代码
classSolution{public:vector<vector<int>>fourSum(vector<int>&nums,inttarget){vector<vector<int>>result;sort(nums.begin(),nums.end());for(intk=0;k<nums.size();k++){//剪枝处理if(nums[k]>target&&nums[k]>=0){break;//这里使用break 同意通过最后的return返回}//对nums[k]去重if(k>0&&nums[k]==nums[k-1]){continue;}for(inti=k+1;i<nums.size();i++){//2级剪枝处理if(nums[k]+nums[i]>target&&nums[k]+nums[i]>=0){break;}//对nums[i]去重if(i>k+1&&nums[i]==nums[i-1]){continue;}intleft=i+1;intright=nums.size()-1;while(left<right){if((long)nums[k]+nums[i]+nums[left]+nums[right]>target){right--;}elseif((long)nums[k]+nums[i]+nums[left]+nums[right]<target){left++;}else{result.push_back(vector<int>{nums[k],nums[i],nums[left],nums[right]});//对nums[left]和nums[right]去重while(left<right&&nums[right]==nums[right-1])right--;while(left<right&&nums[left]==nums[left+1])left++;//找到答案时，双指针同时收缩right--;left++;}}}}returnresult;}};