算法修炼之路之滑动窗口
目录
一：滑动窗口的认识及模板
这里先通过一道题来引出滑动窗口
画图分析：
具体代码:
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.第一题
画图分析:
具体代码:
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.第二题
画图分析:
具体代码:
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.第三题
画图分析:
具体代码：
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.第四题
画图分析:
具体代码:
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.第五题
画图分析：
具体代码:
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++;//进窗口+维护count
if(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.第六题
画图分析:
具体代码:
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;//进窗口+维护count
if(right-left+1>len*m)//判断
{
string out=s.substr(left,len);
if(hash1.count(out) && hash2[out]--<=hash1[out]) --count;//出窗口+维护count
left+=len;
}
if(count==m) ret.push_back(left);//更新结果
}
}
return ret;
}7.第七题
画图分析:
具体代码:
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;//进窗口+维护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--;//出窗口+维护count
}
}
if(begin==-1) return "";
else return s.substr(begin,minlen);
}原文地址：https://blog.csdn.net/Miwll/article/details/142706715
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！