创作不易，感谢三连
一.长度最小的数组
class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int len=INT_MAX,n=nums.size(),sum=0;//len必须要给一个很大的数，否则 for(int left=0,right=0;right<n;++right) { sum+=nums[right];//right进窗口 while(sum>=target)//符合条件后进行更新，然后出窗口 { len=min(len,right-left+1);//更新长度 sum-=nums[left++]; } } return len==INT_MAX?0:len; } };
二.无重复字符的最长字串
class Solution { public: int lengthOfLongestSubstring(string s) { int hash[128]={};//计数 int len=0, n=s.size(); for(int left=0,right=0;right<n;++right) { ++hash[s[right]];//进窗口 while(hash[s[right]]>1) --hash[s[left++]];//出窗口 len=max(len,right-left+1);//更新长度 } return len; } };
三.最大连续1的个数
class Solution { public: int longestOnes(vector<int>& nums, int k) { int len=0; for(int left=0,right=0,zero=0;right<nums.size();++right) { if(nums[right]==0) ++zero;//进窗口 while(zero>k) if(nums[left++]==0) --zero;//出窗口 len=max(len,right-left+1); } return len; } };
四.将x减到0的最小操作数
class Solution { public: int minOperations(vector<int>& nums, int x) {//将问题转化为求一个最长子数组 其大小正好==sum-x int ret=-1; int sum=accumulate(nums.begin(),nums.end(),0);//计算数组的总和 int target=sum-x;//记录目标值 if(target<0) return -1;//细节处理 for(int left=0,right=0,temp=0,n=nums.size();right<n;++right) { temp+=nums[right];//进窗口 while(temp>target) temp-=nums[left++];//出窗口 if(temp==target) ret=max(ret,right-left+1);//更新结果 } return ret==-1?-1:nums.size()-ret; } };
五.水果成篮
class Solution { public: int totalFruit(vector<int>& fruits) { int hash[100001]={0}; int ret=0,n=fruits.size(); for(int left=0,right=0,kinds=0;right<n;++right) { if(hash[fruits[right]]++==0) ++kinds;//进窗口 while(kinds>2) if(--hash[fruits[left++]]==0) --kinds; ret=max(ret,right-left+1); } return ret; } };
六.找到字符串种所有字母异位词
class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> ret; int hash1[26]={0};//用来统计p的元素个数 for(char ch:p) ++hash1[ch-'a']; int hash2[26]={0};//用来统计滑动窗口的元素个数 int m=p.size(); for(int left=0,right=0,count=0;right<s.size();++right)//count用来记录有效字符的个数 { char in=s[right]; if(++hash2[in-'a']<=hash1[in-'a']) ++count;//进窗口的同时统计有效字符个数 if(right-left+1>m)//判断 出窗口 { char out=s[left++]; if(hash2[out-'a']--<=hash1[out-'a']) --count; } if(count==m) ret.push_back(left); } return ret; } };
七.最小覆盖字串
class Solution { public: string minWindow(string s, string t) { int hash1[128]={0};//统计t字符串个元素的出现次数 int kinds=0;//用来统计种类 for(char ch:t) if(hash1[ch]++==0) ++kinds; int hash2[128]={0};//统计s字符串中滑动窗口的元素出现次数 int begin=-1,minlen=INT_MAX;//用来记录返回值情况 for(int left=0,right=0,count=0;right<s.size();++right) { if(++hash2[s[right]]==hash1[s[right]]) ++count;//进窗口的同时统计窗口内元素种类 while(count==kinds)//当种类都一样时，可以去更新结果 { if(right-left+1<minlen)//因为还需要更新begin，所以不能直接用min { minlen=right-left+1; begin=left; } if(hash2[s[left]]--==hash1[s[left]]) --count; ++left; } } return begin==-1?"":s.substr(begin,minlen); } };
八.串联所有单词的子串
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { int m=words.size();//单词个数 int len=words[0].size();//每个单词的长度 vector<int> ret;//用来返回 unordered_map<string,int> hash1;//用来记录word的各个单词出现次数 for(auto s:words) ++hash1[s]; for(int i=0;i<len;++i)//要使用len次滑动窗口 { unordered_map<string,int> hash2;//用来记录滑动窗口的各个单词出现次数 for(int left=i,right=i,count=0;right+len-1<s.size();right+=len)//count用来有效子串 { string in=s.substr(right,len); if(++hash2[in]<=hash1[in]) ++count;//进窗口顺便维护count if(right-left+1>len*m)//如果超过窗口的大小，就要出窗口 { string out=s.substr(left,len); if(hash2[out]--<=hash1[out]) --count; //出窗口前要先维护count left+=len;//出窗口要更新left } if(count==m) ret.push_back(left);//如果count==m，说明有效子串达到要求 } } return ret; } };
九.滑动窗口总结
当题目涉及到子串或者是子数组，都可以考虑到使用滑动窗口来进行解决
但是有一个需要注意的地方就是如果涉及到窗口求和的话。要保证数都是正整数，否则就不满足单调性。如下图这一题
涉及到不同的种类需要统计数量的时候，常常会用到哈希表！！ （5-7题）
后面有类似题目会持续更新！！
