算法修炼之路之滑动窗口

目录

一：滑动窗口的认识及模板

二：LeetcodeOJ练习 

1.第一题

2.第二题 

3.第三题 

4.第四题 

5.第五题 

 6.第六题

7.第七题

一：滑动窗口的认识及模板

这里先通过一道题来引出滑动窗口

LeetCode 209 长度最小的子数组

画图分析： 

 具体代码:

int minSubArrayLen(int target, vector<int>& nums) {int sum=0,ret=INT_MAX;int left=0,right=0;while(right<nums.size()){sum+=nums[right++];//进窗口while(sum>=target)//判断{ret=min(ret,right-left);//更新结果sum-=nums[left++];//出窗口}}return  ret==INT_MAX? 0:ret;}

二：LeetcodeOJ练习 

1.第一题

 LeetCode_3 无重复字符的最长子串

 画图分析:

具体代码:

int lengthOfLongestSubstring(string s) {int hash[129]={0};int ret=0;for(int left=0,right=0;right<s.size();++right){hash[s[right]]++;//进窗口while(hash[s[right]]>1)//判断{hash[s[left++]]--;//出窗口}ret=max(ret,right-left+1);//更新结果}return ret;}

2.第二题 

 LeetCode_1004 最大连续1的个数III

画图分析:

具体代码:

int longestOnes(vector<int>& nums, int k) {int zero=0,ret=0;for(int left=0,right=0;right<nums.size();++right){if(nums[right]==0) zero++;//进窗口while(zero>k)//判断{if(nums[left++]==0) zero--;//出窗口}ret=max(ret,right-left+1);//更新结果}return ret;}

3.第三题 

 LeetCode-1658 将x减到0的最小操作数

画图分析:

具体代码：

int minOperations(vector<int>& nums, int x) {int sum=0;//计算数组和for(int e:nums) sum+=e;int target=sum-x;if(target<0) return -1;int ret=-1;for(int left=0,right=0,tmp=0;right<nums.size();++right){tmp+=nums[right];//进窗口while(tmp>target)//判断{tmp-=nums[left++];//出窗口}if(tmp==target) ret=max(ret,right-left+1);//更新结果}if(ret==-1) return -1;else return nums.size()-ret;}

4.第四题 

LeetCode_904 水果成篮

画图分析:

 

具体代码:

int totalFruit(vector<int>& f) {unordered_map<int,int> hash;//统计窗口中水果的种类数int ret=0;for(int left=0,right=0;right<f.size();++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;}

5.第五题 

 LeetCode_438 找到字符串中所有的字母异位词

画图分析：

具体代码:

vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[26]={0};//统计字符串p中字符个数for(auto e:p) hash1[e-'a']++;int len=p.size();int hash2[26]={0};//统计窗口中出现字符的个数for(int left=0,right=0,count=0;right<s.size();right++){char in=s[right];if(++hash2[in-'a']<=hash1[in-'a']) count++;//进窗口+维护countif(right-left+1>len)//判断{char out=s[left++];if(hash2[out-'a']--<=hash1[out-'a']) count--;//出窗口+维护count}//更新结果if(count==len) ret.push_back(left);}return ret;}

 6.第六题

LeetCode_30 串联所有单词的子串

画图分析:

具体代码:

 vector<int> findSubstring(string s, vector<string>& words) {unordered_map<string,int> hash1;//统计words中单词的次数for(auto e:words) hash1[e]++;vector<int> ret;int len=words[0].size(),m=words.size();for(int i=0;i<len;++i)//执行len次{unordered_map<string,int> hash2;for(int left=i,right=i,count=0;right<s.size();right+=len){string in=s.substr(right,len);if(hash1.count(in) && ++hash2[in]<=hash1[in]) ++count;//进窗口+维护countif(right-left+1>len*m)//判断{string out=s.substr(left,len);if(hash1.count(out) && hash2[out]--<=hash1[out]) --count;//出窗口+维护countleft+=len;}if(count==m) ret.push_back(left);//更新结果}}return ret;}

7.第七题

LeetCode_76 最小覆盖子串

画图分析:

具体代码: 

 string minWindow(string s, string t) {int hash1[128]={0};//统计字符串t中每个字符出现的次数int kinds=0;//统计字符串t中有效字符的种类for(auto ch:t)if(hash1[ch]++==0) kinds++;int hash2[128]={0};//统计窗口中出现字符的次数int minlen=INT_MAX,begin=-1;for(int left=0,right=0,count=0;right<s.size();++right){char in=s[right];if(++hash2[in]==hash1[in]) ++count;//进窗口+维护countwhile(count==kinds)//判断条件{if(right-left+1<minlen)//更新结果{minlen=right-left+1;begin=left;} char out=s[left++];if(hash2[out]--==hash1[out]) count--;//出窗口+维护count}}if(begin==-1) return "";else return s.substr(begin,minlen);}