目录
- 知识框架
- No.0 筑基
- 知识框架
- 滑动窗口核心原理
- No.1 字符串滑动窗口
- 题目来源：LeetCode-3. 无重复字符的最长子串
- 题目来源：LeetCode-438. 找到字符串中所有字母异位词
- 题目来源：LeetCode-76. 最小覆盖子串
- No.2 数组滑动窗口
- 题目来源：LeetCode-209-长度最小的子数组
- 题目来源：蓝桥杯-第十四届模拟-附近最小
知识框架
No.0 筑基
请先学习下知识点，道友！
题目知识点大部分来源于此：题目例题大部分来源于此：
知识框架
滑动窗口 =同向双指针
核心思想：用一个指针控制窗口右端点，另一个指针动态调整窗口左端点，把O(n²)暴力解法优化成O(n) 线性解法。
滑动窗口核心原理
- 暴力解法：两个for循环，枚举所有子区间 → 时间复杂度 O(n²)
- 滑动窗口：
- 只用一个for循环遍历窗口右端点
right - 用
while/条件动态收缩窗口左端点left - 全程只遍历一次数组/字符串 →O(n) 效率
- 只用一个for循环遍历窗口右端点
一句话口诀：固定右，收缩左，窗口动，结果出
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。
在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。
那么滑动窗口如何用一个for循环来完成这个操作呢?
首先要思考 如果用一个for循环，那么应该表示 滑动窗口的起始位置，还是终止位置?
如果只用一个for循环来表示 滑动窗口的起始位置，那么如何遍历剩下的终止位置？
此时难免再次陷入 暴力解法的怪圈。
所以 只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。
那么问题来了， 滑动窗口的起始位置如何移动呢？
No.1 字符串滑动窗口
题目来源：LeetCode-3. 无重复字符的最长子串
题目描述：
题目思路：
题目代码：
classSolution{public:intlengthOfLongestSubstring(string s){// 滑动窗口，感觉像是 同向双指针// 不过滑动窗口更像是 固定一个right，内部while的同时移动left// 虽然像是 同向双指针，但是在固定 一个right之后行为方式更像双端指针了unordered_map<char,int>mp;intn=s.size();intleft=0,right=0;intmaxLen=0;for(right=0;right<n;right++){mp[s[right]]++;while(mp[s[right]]>1){mp[s[left]]--;left++;}maxLen=max(maxLen,right-left+1);}returnmaxLen;}};classSolution{public:intlengthOfLongestSubstring(string s){intlen=s.size();map<char,int>mp;intans=0;for(inti=0,j=0;j<len;j++){//先判断右边指向的是否在窗口内；//在里面if(mp[s[j]]==1){while(mp[s[j]]==1){mp[s[i]]=0;i++;}}mp[s[j]]=1;ans=max(ans,j-i+1);}returnans;}};classSolution{public:intlengthOfLongestSubstring(string s){// 滑动窗口，感觉像是 同向双指针// 不过滑动窗口更像是 固定一个right，内部while的同时移动left// 虽然像是 同向双指针，但是在固定 一个right之后行为方式更像双端指针了intn=s.size();if(n==0)return0;unordered_set<char>lookup;intmaxx=0;intleft=0;for(intright=0;right<n;right++){// 开始位置while(lookup.find(s[right])!=lookup.end()){//找到的话 left要左移动了lookup.erase(s[left]);left++;}maxx=max(maxx,right-left+1);lookup.insert(s[right]);}returnmaxx;}};题目来源：LeetCode-438. 找到字符串中所有字母异位词
题目描述：
题目思路：
感觉和双指针差不多，第一个想到的就是暴力循环的超时的版本
这个是定长的 滑动窗口，就是说 right++ left++ ,然后维持住 使得 这个窗口中的判断尽量超级简单即可
题目代码：
classSolution{public:vector<int>findAnagrams(string s,string p){// p小 s大// 定长滑动窗口 ， 如果固定右侧的话// 感觉如果找到第一个，那么后面的就容易了// 搞个数组， 如果两个数组相等就可以了，完美// 然后向右边移动的时候进行 left的对应的减， right对应的加ints_n=s.size();intp_n=p.size();if(p_n>s_n)return{};vector<int>ans_p(26,0);vector<int>ans_s(26,0);for(auto&ch:p)ans_p[ch-'a']++;vector<int>res;intleft=0,right=0;for(right=0;right<s_n;right++){autoch=s[right];ans_s[ch-'a']++;if(right-left+1<p_n)continue;if(ans_s==ans_p){res.push_back(left);}ans_s[s[left]-'a']--;left++;}returnres;}};classSolution{public:vector<int>findAnagrams(string s,string p){// p小 s大// 定长滑动窗口 ， 如果固定右侧的话// 感觉如果找到第一个，那么后面的就容易了// 搞个数组， 如果两个数组相等就可以了，完美// 然后向右边移动的时候进行 left的对应的减， right对应的加std::vector<int>res;intm=s.size();intn=p.size();if(m<n)returnres;std::vector<int>s_v(26,0);std::vector<int>p_v(26,0);for(autoch:p)p_v[ch-'a']++;intleft=0;intright=left+n-1;for(inti=0;i<n;i++){s_v[s[i]-'a']++;}// 定长滑动窗口while(right<m){if(s_v==p_v)res.push_back(left);s_v[s[left]-'a']--;left++;right++;if(right>=m)break;s_v[s[right]-'a']++;}returnres;}};题目来源：LeetCode-76. 最小覆盖子串
题目描述：
题目思路：
题目代码：
classSolution{public:boolis_cover(vector<int>&a,vector<int>&b){for(inti=0;i<128;i++){if(a[i]<b[i])returnfalse;}returntrue;}stringminWindow(string s,string t){// 一般这种都是滑动窗口// 如果按照之前那个就是 对于t的话每个位置++// 然后是 对于s 进行滑动窗口// 但是怎么滑动呢？// 像这种子串肯定要用 char-'a' 来计数的// 假设现将t进行计数，然后呢就是滑动窗口了，// left， right，固定右边，左侧向右滑动，intt_n=t.size();ints_n=s.size();vector<int>ans_s(128,0);vector<int>ans_t(128,0);for(auto&ch:t)ans_t[ch-'A']++;intleft=0,right=0;intminLen=INT_MAX;intminStart=0;for(right=0;right<s.size();right++){autoch=s[right];ans_s[ch-'A']++;while(is_cover(ans_s,ans_t)){if(right-left+1<minLen){minLen=min(minLen,right-left+1);minStart=left;}ans_s[s[left]-'A']--;left++;}}if(minLen==INT_MAX)return"";returns.substr(minStart,minLen);}};classSolution{public:boolis_cover(vector<int>&a,vector<int>&b){for(inti=0;i<128;i++){if(a[i]<b[i])returnfalse;}returntrue;}stringminWindow(string s,string t){// 一般这种都是滑动窗口// 如果按照之前那个就是 对于t的话每个位置++// 然后是 对于s 进行滑动窗口// 但是怎么滑动呢？// 像这种子串肯定要用 char-'a' 来计数的// 假设现将t进行计数，然后呢就是滑动窗口了，// left， right，固定右边，左侧向右滑动，std::vector<int>s_vc(128,0);std::vector<int>t_vc(128,0);for(autoch:t)t_vc[ch-'A']++;intm=s.size();intn=t.size();// 处理边界情况，避免越界if(m<n||m==0||n==0){return"";}intleft=0;intright=left+n-1;intminn=0x3f3f3f3f;intminn_start=0;string res="";for(inti=0;i<n;i++)s_vc[s[i]-'A']++;if(is_cover(s_vc,t_vc)){minn_start=left;minn=min(minn,right-left+1);}for(right++;right<m;right++){s_vc[s[right]-'A']++;while(is_cover(s_vc,t_vc)){if((right-left+1)<minn){minn_start=left;minn=min(minn,right-left+1);}s_vc[s[left]-'A']--;left++;}}if(minn==0x3f3f3f3f)returnres;res=s.substr(minn_start,minn);returnres;}};No.2 数组滑动窗口
题目来源：LeetCode-209-长度最小的子数组
题目描述：
题目思路：
滑动窗口的题目；
题目代码：
classSolution{public:intminSubArrayLen(inttarget,vector<int>&nums){// 很正常的就顺下来了intn=nums.size();intleft=0,right=0;intsum=0;intminLen=INT_MAX;for(right=0;right<n;right++){sum=sum+nums[right];while(sum>=target){minLen=min(minLen,right-left+1);sum=sum-nums[left];left++;}}if(minLen==INT_MAX)return0;returnminLen;}};classSolution{public:intminSubArrayLen(ints,vector<int>&nums){intresult=INT32_MAX;intsum=0;// 滑动窗口数值之和inti=0;// 滑动窗口起始位置intsubLength=0;// 滑动窗口的长度for(intj=0;j<nums.size();j++){sum+=nums[j];// 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件while(sum>=s){subLength=(j-i+1);// 取子序列的长度result=result<subLength?result:subLength;sum-=nums[i++];// 这里体现出滑动窗口的精髓之处，不断变更i（子序列的起始位置）}}// 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列returnresult==INT32_MAX?0:result;}};题目来源：蓝桥杯-第十四届模拟-附近最小
题目描述：
题目思路：
题目代码：
#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=1e7+10;intq[N];inta[N];intb[N];intn,k;intsum;/* * 滑动窗口是从寻找到的位置i开始算长度的 * 而这个是从i-k开始算的，所以题目可以转换为 * 原数组n+2k个元素，然后从1开始遍历，滑动窗口长度为2*k+1 * 记得初始化前k个元素和后k个元素极大值如1e18，这样就可以防止初值0造成影响 */voidmin_q(){inth=1,t=0;intlen=2*k+1;for(inti=1;i<=n+2*k;i++){while(h<=t&&q[h]+len<=i)h++;while(h<=t&&b[i]<b[q[t]])t--;q[++t]=i;if(i>=len){cout<<b[q[h]]<<" ";}}cout<<endl;}intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];cin>>k;for(inti=1;i<=k;i++)b[i]=1e18;for(inti=k+n+1;i<=n+2*k;i++)b[i]=1e18;for(inti=k+1;i<=k+n;i++)b[i]=a[i-k];//for (int i = 1; i <= n + 2 * k; i++)cout << b[i] << " ";//cout << endl;min_q();return0;}
