454、四數相加Ⅱ
·map哈希表
當初不知四數相加的好，做完四數之和發現~oh 這題真簡單
題目鏈接：https://leetcode.cn/problems/4sum-ii/
前提：計算四個陣列中多少個元組滿足條件（值可以重復）
思路：四個陣列分別兩兩相加|時間復雜度O(n^2)
???前兩個陣列相加的值作為map的鍵
???map中查找等于（0-后兩個陣列相加的值）的鍵
???找到則+該鍵值（這個值可能大于一）
代碼實作：unordered_map哈希表
?????時間復雜度O(n^2)
?????空間復雜度O(n)
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> umap;
int count=0;
for(int i1:nums1){
for(int i2:nums2){
umap[i1+i2]++;
}
}
for(int i3:nums3){
for(int i4:nums4){
if(umap.find(0-(i3+i4))!=umap.end())count=count+umap[0-(i3+i4)];
}
}
return count;
}
};
識訓摘要：map哈希法O(n ^2)比暴力O(n ^4)要快
學習的文章鏈接：https://programmercarl.com/0454.四數相加II.html
383、贖金信
·陣列哈希表
為了寫一封完整的信，咔咔剪雜志doge
題目鏈接：https://leetcode.cn/problems/ransom-note/
前提：nums1中每個字符只能使用一次
???陣列中只有小寫字母
思路：使用長度為26的陣列//對應26個小寫字母
???遍歷nums1，對應陣列++
???遍歷nums2，對應陣列--
???陣列中有數<0則false
代碼實作：陣列哈希表
?????時間復雜度O(n)
?????空間復雜度O(1)
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int num[26]={0};
for(char i:magazine){
num[i-'a']++;
}
for(char i:ransomNote){
num[i-'a']--;
}
for(int j:num){
if(j<0)return false;
}
return true;
}
};
識訓摘要：剪雜志很解壓doge
?????<0回傳false，因為雜志沒有對應的字母！
?????遍歷前可以添加下列代碼來減少計算：
if (ransomNote.size() > magazine.size()) {
return false;
}
學習的文章鏈接：https://programmercarl.com/0383.贖金信.html
15、三數之和
·雙指標yyds
重難點：去重
題目鏈接：https://leetcode.cn/problems/3sum/
前提：一個整數陣列，值不重復的三元組
???3<=nums.length<=3000
思路：首先進行陣列排序，方便比較和去重
???i遍歷陣列+雙指標法
???先排除i>0的情況?//減少運算
???再不看i=i-1?//去重
???i，i+1和nums.size()-1三個指標所指數值之和sum與0相比：
??????大于零尾巴指標向前移，小于零頭部指標向后移，
??????等于零存入結果并對下一步進行去重
代碼實作：雙指標法
?????時間復雜度O(n^2)(小于？)
?????空間復雜度O(n)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(),nums.end());
int left,right,sum;
for(int i=0;i<nums.size()-2;i++){
if(nums[i]>0)return result;
if(i>0&&nums[i]==nums[i-1])continue;
left=i+1;
right=nums.size()-1;
while(left<right){
sum=nums[i]+nums[left]+nums[right];
if(sum==0){
result.push_back(vector<int>{nums[i],nums[left],nums[right]});
left++;//找到一個三元組后，收縮
right--;
while(left<right&&nums[left]==nums[left-1])left++;
while(left<right&&nums[right]==nums[right+1])right--;//left<right，防止下標越界
}
else{
if(sum>0)right--;
if(sum<0)left++;
}
}
}
return result;
}
};
識訓摘要：去重要考慮邊界和一些特殊情況，雙指標咔咔剪枝doge
學習的文章鏈接：https://programmercarl.com/0015.三數之和.html#哈希解法
18、四數之和
·雙指標法plus
套娃，三數之和又套了一層
題目鏈接：https://leetcode.cn/problems/4sum/submissions/
前提：一個整數陣列，值不重復的四元組
???-10^9 <= target <= 10^9
???1 <= nums.length <=200
思路：在三數之和的思路基礎上，再套一層回圈
代碼實作：雙指標plus
?????時間復雜度O(n^3)
?????空間復雜度O(n)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> result;
int i,j,left,right;
long sum;
sort(nums.begin(),nums.end());
for(i=0;i<nums.size()-3;i++){
if(nums.size()<4)return result;//陣列過短，直接回傳result
if(nums[i]>target&&target>=0)return result;
if(i>0&&nums[i]==nums[i-1])continue;
for(j=i+1;j<nums.size()-2;j++){
if(j>i+1&&nums[j]==nums[j-1])continue;//外面多了一層i，所以j>i+1保證j=i+1已經遍歷過了
left=j+1;
right=nums.size()-1;
while(left<right){
sum=(long)nums[i]+(long)nums[j]+(long)nums[left]+(long)nums[right];//啊,這...int相加超范圍了
if(sum==target){
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--;
}
else{
if(sum>target)right--;
if(sum<target)left++;
}
}
}
}
return result;
}
};
識訓摘要：剪枝操作要注意數值范圍！在升序排序后，target<0和target>0的情況不同，不要把需要的值也剪了，
?????去重多考慮數值變化和邊界，
?????注意int范圍，相加可能溢位！
學習的文章鏈接：https://programmercarl.com/0018.四數之和.html#其他語言版本
學習的視頻鏈接：https://www.bilibili.com/video/BV1DS4y147US/?spm_id_from=333.788&vd_source=c2b246a405f861a2b3c13ab2b1b1eea6
學習時長：4h40min
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/525035.html
標籤：其他
上一篇：標記語言-markdown