目录
一:滑动窗口的认识及模板
二: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);}