代码随想录第六天|454.四数相加II 383. 赎金信 15. 三数之和 18. 四数之和
454.四数相加
思路：暴力解法O(n^4）如何降低时间复杂度呢 可以利用哈希表 储存ab数组之和的出现次数
然后再遍历cd数组 寻找-c+d find时间复杂度为1 所以时间复杂度为O(n^2)
class Solution {
public:int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {unordered_map<int,int> m;//代表 a+b和出现次数的映射for(int num1:nums1){for(int num2:nums2){m[num1+num2]++;}}int res=0;//遍历每一种可能for(int num3:nums3){for(int num4:nums4){//说明找到了mif(m.find(-(num3+num4))!=m.end()){res+=m.find(-(num3+num4))->second;}}}return res;}
};383.赎金信
思路：本题就是在magazine能否找到random所有的字符 暴力解法
遍历random每一个字符 在magazine寻找 若是找到break 直到结束 同时记录flag
若是本次循环没找到直接return false 时间复杂度为O(n*m)
降低时间复杂度：
遍历两个字符串记录出现次数
O(n) 然后在magazine找字母 有空间换时间就是哈希表
class Solution {
public:bool canConstruct(string ransomNote, string magazine) {vector<int> word1(26,0);vector<int> word2(26,0);for(int i=0;i<ransomNote.size();i++){word1[ransomNote[i]-'a']++;}for(int i=0;i<magazine.size();i++){word2[magazine[i]-'a']++;}//现在我们获得每个单词的字母出现顺序 for(int i=0;i<26;i++){//如果magazine的字母数量小returnfalseif(word1[i]>word2[i])return false;}return true;}
};三数之和
思路：没有什么思路 直接看代码随想录
双指针法：在改变left和right的时候我思考过会不会漏掉一些情况
关键在于去重abc
class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> res;sort(nums.begin(),nums.end());for(int i=0;i<nums.size();i++){//最小值大于0 退出循环if(nums[i]>0)break;if(i>0&&nums[i]==nums[i-1])continue;//对i去重 已经遍历过 肯定不需要遍历了int left=i+1;int 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{res.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++;right--;left++;}}}return res;}
};四数之和
思路：和三数之和相同原理需要多练多理解
class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> result;sort(nums.begin(),nums.end());//两层遍历确定一个数值 然后 双指针找剩下两个 降低o(n)时间复杂度for(int k=0;k<nums.size();k++){//可能都是负数 向下遍历还有结果 和0不一样if(nums[k]>target&&nums[k]>=0)break;if(k>0&&nums[k]==nums[k-1])continue;for(int i=k+1;i<nums.size();i++){if(nums[k]+nums[i]>target&&nums[k]+nums[i]>=0)break;if(i>k+1&&nums[i]==nums[i-1])continue;int left=i+1;int right=nums.size()-1;while(right>left){if ((long) nums[k] + nums[i] + nums[left] + nums[right] > target) {right--;// nums[k] + nums[i] + nums[left] + nums[right] < target 会溢出} else if ((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 (right > left && nums[right] == nums[right - 1]) right--;while (right > left && nums[left] == nums[left + 1]) left++;// 找到答案时，双指针同时收缩right--;left++;}}}}return result;}
};感觉还是没太理解这个双指针法需要二刷：
大概思路是我先确定第一个元素
然后剪枝 break 都大于0了 没有必要继续循环来 去重 continue 之前肯定已经遍历过了
再确定第二个元素 剪枝 去重
然后双指针寻找元素
本题关键在于寻找不重复的数组组合 -1 -1 2 2 这样只算一个 -1 -1 2
这样我们一定要先排序 所有得到结果都是从小到大的 是有序的
然后去思考怎末得到不重复的数组 首先就是 之前遍历过的