滑动窗口的思想是：
1、设定前指针和后指针，先向后移动后指针直到满足条件，
2、然后向后移动前指针判断是否仍满足条件，
3、如果不满足条件继续向后移动后指针直到满足条件，找出满足条件的最短序列即可。
class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { //先计算部分和 int *donser,sum=0,size=nums.size(); donser=new int[size]; for(int i=0;i<size;i++) { sum+=nums[i]; donser[i]=sum; } //滑动窗 int up=0,down=1,lable_min=size; if(size<=1) { if(size<1) return 0; else if(nums[0]>=s) return 1; else return 0; } if(donser[size-1]<s) return 0; if(donser[0]>=s) return 1; while(down<size) { int sum_now; if(up==0) sum_now=donser[down]; else sum_now=donser[down]-donser[up-1]; if(sum_now<s) { down++; continue; } if(sum_now>=s) { if(down-up+1<lable_min) lable_min=down-up+1; up++; } } return lable_min; } };
注意特值和边界
计算局部和可以简化计算
leedcode 438. 找到字符串中所有字母异位词
窗口长度固定，滑动比较即可，模式串的顺序不重要因此用了map存模式串，注意map会为key自动排序
bool cmp(map<char,int>donser,map<char,int>tmp) { map<char,int>::iterator it1=donser.begin(); int lable=0; for(;it1!=donser.end();it1++) { if(it1->second==tmp[it1->first]) continue; else lable=1; } if(lable==1) return false; return true; } class Solution { public: vector<int> findAnagrams(string s, string p) { map<char,int>donser; map<char,int>tmp; vector<int>result; if(s.size()<p.size()||p.size()==0) return result; for(int i=0;i<p.size();i++) { donser[p[i]]++; tmp[s[i]]++; } int up=0,down=p.size()-1; while(down<s.size()) { if(cmp(donser,tmp)==true) { result.push_back(up); } tmp[s[up]]--; up++; down++; tmp[s[down]]++; } return result; } };
leedcode 76. 最小覆盖子串
此题找最短的覆盖子串，最少要遍历一遍，用map会超时，改用数组记录可以通过，前后指针和前面一样
bool cmp(int *donser,int *tmp) { int lable=0; for(int i=0;i<255;i++) { if(donser[i]<=tmp[i]) continue; else { lable=1; break; } } if(lable==1) return false; return true; } class Solution { public: string minWindow(string s, string p) { int donser[256],tmp[256]; memset(donser,0,sizeof(donser)); memset(tmp,0,sizeof(tmp)); string result; if(s.size()<p.size()||p.size()==0) return result; for(int i=0;i<p.size();i++) { donser[int(p[i]-0)]++; tmp[int(s[i]-0)]++; } int up=0,down=p.size()-1,length=s.size(); while(true) { bool cp=cmp(donser,tmp); if(down>=s.size()&&up>=s.size()-p.size()||down-up+1<p.size()) break; if(cp==true) { if(down-up+1<=length) { length=down-up+1; result.assign(s,up,length); } tmp[int(s[up]-0)]--; up++; continue; } if(cp==false&&down<s.size()) { down++; tmp[int(s[down]-0)]++; continue; } if(down>=s.size()&&cp==false) break; } return result; } };
leetcode 3. 无重复字符的最长子串
map存出现的字符位置，start标记当前扫描的头位置，max记录最大长度
class Solution { public: int lengthOfLongestSubstring(string s) { map<char,int>mmp; int start=1; int max_len=0; if(s.size()<=1) return s.size(); for(int i=0;i<=s.size();i++) { if(i==s.size())//查询完毕 { max_len=(i-start>max_len?i-start:max_len); break; } if(mmp[s[i]]==0||(mmp[s[i]]!=0&&mmp[s[i]]<start)) //第一次出现 or 可覆盖 { mmp[s[i]]=i+1; } else if(mmp[s[i]]!=0&&mmp[s[i]]>=start) //不是第一次出现 & 不可覆盖 { max_len=(i-start>max_len?i-start:max_len); start=mmp[s[i]]+1;//更新start mmp[s[i]]=i+1;//覆盖 } } return max_len+1; } };