经典滑动窗口试题（二）

📘北尘_：个人主页
🌎个人专栏:《Linux操作系统》《经典算法试题 》《C++》 《数据结构与算法》

☀️走在路上，不忘来时的初心

---

一、水果成篮

1、题目讲解

2、讲解算法思路

3、代码实现

class Solution {
public:int totalFruit(vector<int>& f) {int n=f.size();unordered_map<int,int> hash;int ret=0;for(int left=0,right=0;right<n;right++){hash[f[right]]++;while(hash.size()>2){hash[f[left]]--;if(hash[f[left]]==0){hash.erase(f[left]);}left++;}ret=max(ret,right-left+1);}return ret;}};

---

二、找到字符串中所有字母异位词

1、题目讲解

2、讲解算法思路

3、代码实现

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[256]={0},len=p.size();for(char ch:p) hash1[ch]++;int hash2[256]={0};for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in]++;if(hash2[in]<=hash1[in]) count++;if(right-left+1>len){char out=s[left];if(hash2[out]<=hash1[out]) count--;hash2[out]--;left++;}if(count==len){ret.push_back(left);}}return ret;      }
};

---

三、串联所有单词的子串

1、题目讲解

2、讲解算法思路

3、代码实现

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string,int> hash1;for(auto ch:words){hash1[ch]++;}int len=words[0].size(),m=words.size();for(int i=0;i<len;i++){unordered_map<string,int> hash2;for(int left=i,right=i,count=0;right+len<=s.size();right+=len){string in=s.substr(right,len);hash2[in]++;if(hash1.count(in) && hash2[in]<=hash1[in]) count++;if(right-left+1>len*m){string out=s.substr(left,len);if(hash1.count(out) && hash2[out]<=hash1[out]) count--;hash2[out]--;left+=len;}if(count==m) ret.push_back(left);}}return ret;}
};

---

四、最小覆盖子串

1、题目讲解

2、讲解算法思路

3、代码实现

代码一

class Solution {
public:string minWindow(string s, string t) {int hash1[256]={0};int kinds=0;for(auto ch:t){if(hash1[ch]==0) kinds++;hash1[ch]++;}int hash2[256]={0};int minlen=INT_MAX,begin=-1;for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in]++;if(hash2[in]==hash1[in])  count++;while(count==kinds){if(right-left+1<minlen){minlen=right-left+1;begin=left;}char out=s[left++];if(hash2[out]--==hash1[out])  count--;    } }if(begin==-1) return "";else return s.substr(begin,minlen);}
};

代码二 不使用kinds来计算种类

class Solution {
public:string minWindow(string s, string t) {int hash1[256]={0},n=t.size();for(char ch:t){hash1[ch]++;}int begin=-1,len=INT_MAX;int hash2[256]={0};for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];hash2[in]++;if(hash2[in]<=hash1[in]) count++;while(count==n){if(right-left+1<len){begin=left;len=right-left+1;}char out=s[left];if(hash2[out]<=hash1[out]) count--;hash2[out]--;left++;}}if(begin==-1) return "";else return  s.substr(begin,len);}};

---