C++算法 滑动窗口篇（下）

目录

一、水果成蓝

1.题目

​编辑

2.核心思路

3.举例模拟

4.代码参考

5.复杂度

二、找到字符串中所有字母异位词

1.题目

​编辑

2.核心思路

3.举例模拟

4.代码参考

5.复杂度

三、串联所有单词的子串

1.题目

​编辑

2.核心思路

3.举例模拟

4.代码参考

5.复杂度

四、最小覆盖子串

1.题目

​编辑

2.核心思路

3.举例模拟

4.代码参考

5.复杂度

五、总结

一、水果成蓝

1.题目

2.核心思路

题意：找最长子数组，里面最多只有 2 种不同数字。

算法：滑动窗口（双指针，left、right）

right 不断向右扩张窗口，把水果加入哈希数组统计数量

count记录当前窗口内水果种类数

一旦count>2，说明窗口非法，移动 left 收缩窗口，直到种类 ≤2

每次窗口合法后，计算窗口长度，更新最大长度ret

hash 数组充当频次表：hash [x] = 窗口内 x 出现次数

3.举例模拟

样例：f = [1,2,1,2,3]初始：left=0, count=0, ret=0, hash 全 0

表格

最终返回 4

4.代码参考

class Solution { public: int totalFruit(vector<int>& f) { int hash[100001]={0}; int ret=0; for(int left=0,right=0,count=0;right<f.size();right++) { //更新count if(hash[f[right]]==0) count++; //进窗口 hash[f[right]]++; while(count>2) { hash[f[left]]--; //出窗口 if(hash[f[left]]==0) count--; left++; } //更新结果 ret=max(ret,right-left+1); } return ret; } };

5.复杂度

时间复杂度：O (n)left 和 right 各自最多从 0 走到 n-1，每个元素最多入窗口一次、出窗口一次，总操作线性。

空间复杂度：O (M)M=100001，是 hash 数组的固定大小；如果值域很大，一般改用 unordered_map，空间是 O (1)（最多存 2 个 key）。

二、找到字符串中所有字母异位词

1.题目

2.核心思路

本题求解字符串s中所有p的字母异位词起始下标，采用固定长度滑动窗口 + 字符频次数组 + 有效字符计数器 count。

1. 数组hash_1[26]统计模式串p中每个小写字母的出现频次；
2. 数组hash_2[26]维护滑动窗口[left, right]内部各字母的频次；
3. count代表窗口内满足「当前频次 ≤ p 中对应字母频次」的有效字符数量：
   • 右指针向右扩张窗口（进窗口）：先将当前字符频次hash_2自增，若增加后的值小于等于hash_1，说明该字符是有效匹配字符，count++；
   • 当窗口长度大于p的长度m，窗口需要收缩：取出左边界字符，先判断当前频次是否满足有效条件，满足则count--，再将频次减 1，左指针右移；
4. 当count == m，说明窗口内有效字符总数等于模式串长度，当前窗口就是p的异位词，记录窗口左端点left。

异位词定义：字符种类、每种字符出现次数完全一致，字符顺序不同。

3.举例模拟

测试样例：s = "cbaebabacd"，p = "abc"，m = 3初始化：hash_1[a]=1,hash_1[b]=1,hash_1[c]=1，其余为 0；left=0,count=0，hash_2全部置 0

表格

最终输出：[0,6]

4.代码参考

class Solution { public: vector<int> findAnagrams(string s, string p) { int m=p.size(); int hash_1[26]={0}; for(auto e: p) { hash_1[e-'a']++; } int hash_2[26]={0}; vector<int> ret; for(int left=0,right=0,count=0;right<s.size();right++) { char in=s[right]; if(++hash_2[in-'a'] <= hash_1[in-'a']) { count++; } if(right-left+1>m) { char out=s[left]; if(hash_2[out-'a'] <= hash_1[out-'a']) { count--; } hash_2[out-'a']--; left++; } if(count==m) { ret.push_back(left); } } return ret; } };

5.复杂度

设 n = s.size(), m = p.size()

时间复杂度：(O(n+m)) 遍历 p 统计频次：(O(m))；滑动窗口只遍历 s 一遍，每个元素只进窗口一次、出窗口一次，无内层循环：(O(n))

空间复杂度：(O(1)) 只固定开辟大小为 26 的数组，和输入规模无关；返回答案数组不计入算法额外空间开销。

三、串联所有单词的子串

1.题目

2.核心思路

前提：words 里所有单词长度相等，记为step，单词总数量n，目标窗口总字符长度 =step * n

1. 先用hash_1统计 words 中每个单词需要出现多少次，作为标准对照。
2. 外层循环for(int i=0;i<step;i++)：枚举起始偏移量 i。 因为我们滑动窗口每次按整块单词（step个字符）移动，不能逐字符滑；一共有0 ~ step-1共step种不同的切分对齐方式，必须分开跑滑动窗口，防止漏掉答案。
3. 对每一个偏移 i，独立开启一套滑动窗口：
   • left：窗口左边界，right：窗口右边界，每次right += step，一次读入一整个单词；
   • hash_2：维护当前窗口内单词频次；
   • count：窗口内符合要求（次数不超过 hash_1）的单词数量，count == n代表窗口匹配成功；
4. 进窗口：读取right位置单词，更新hash_2；如果这个单词是目标单词且新增后次数没有超标，count++；
5. 出窗口：如果当前窗口总长度 >step*n，说明窗口过长，弹出最左侧单词。如果被弹出单词在弹出前是合规的，count--，更新频次、左边界右移；
6. 每次调整完窗口，判断count == n，满足就把left加入结果数组。

优化点：不用每次比较两张哈希表，用 count 变量 O (1) 判断是否匹配成功。

3.举例模拟

样例：s = "barfoothefoobarman",words = {"foo","bar"}

step = 3，n = 2，目标窗口总长 = 6

hash_1: {"foo":1, "bar":1}外层 i 从 0 开始（偏移 0）： 初始化left=0, right=0, count=0, hash_2为空

1. right=0： in = "bar"，hash_2 ["bar"]=1；1<=1 → count=1 窗口长度 0-0+1=1 ≤6，不收缩 count≠2，无结果
2. right=3： in = "foo"，hash_2 ["foo"]=1；1<=1 → count=2 窗口长度 3-0+1=4 ≤6，不收缩 count==2 → left=0 存入答案 ret=[0]
3. right=6： in = "the"，不在 hash_1，count 不变 窗口长度 6-0+1=7 >6 → 触发出窗口 out="bar"，hash_2 ["bar"]=1 ≤1 → count=1；hash_2 ["bar"]-- →0；left=3 count≠2
4. right=9： in="foo"，hash_2 ["foo"]=2 > hash_1 ["foo"]=1 → count 不变 窗口长度 9-3+1=7>6，弹出 out="foo"，hash_2 ["foo"]=2，弹出前 > 1，count 不变；hash_2 ["foo"]--=1；left=6
5. right=12： in="bar"，hash_2 ["bar"]=1 ≤1 → count=2 count==2 → left=9 存入答案 ret=[0,9] 后面继续循环…… i=1、i=2 两个偏移继续单独跑滑动窗口，这组样例没有更多答案。

4.代码参考

class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { unordered_map<string,int> hash_1; for(auto& e:words) { hash_1[e]++; } vector<int> ret; int step=words[0].size(),n=words.size(); for(int i=0;i<step;i++) { unordered_map<string,int> hash_2; for(int left=i,right=i,count=0;right+step<=s.size();right+=step) { //进窗口 string in=s.substr(right,step); hash_2[in]++; if(hash_1.count(in) && hash_2[in]<=hash_1[in]) { count++; } //出窗口 if(right-left+1>step*n) { string out=s.substr(left,step); if(hash_1.count(out) && hash_2[out]<=hash_1[out]) { count--; } hash_2[out]--; left+=step; } //更新结果 if(count==n) { ret.push_back(left); } } } return ret; } };

5.复杂度

设：s长度：S，step：单词长度，n：words 单词数量

时间复杂度：O(step* S) 外层循环执行step次；每一轮内层滑动窗口中，right只会向前移动，每个字符最多被访问一次；哈希表操作平均 O (1)

空间复杂度：O(n）两张哈希表最多存储 words 里所有单词，最多 n 个键值对。

四、最小覆盖子串

1.题目

2.核心思路

这是不定长滑动窗口（双指针）经典题：在s中找包含t全部字符（含对应频次）的最短子串。

1. 用两个数组hash_1、hash_2分别统计t的字符频次、窗口[left, right]内字符频次；
2. key_count：t 中不同字符的种类数；count：窗口内已经满足频次要求的字符种类；
3. 右指针right不断向右扩大窗口，加入字符，当某字符窗口频次等于 t 的频次时，count++；
4. 当count == key_count，说明当前窗口已经覆盖 t 全部字符，进入收缩阶段：
   • 尝试移动左指针left缩小窗口，更新最短子串；
   • 如果被移出的字符，移出前刚好等于 t 需要的频次，count--，退出收缩循环；
5. 全程记录最优窗口起点begin和长度len，最后截取返回。

重点：不是 “出现过” 就行，要满足数量，比如t="AABC"，窗口里 A 必须≥2、B≥1、C≥1。

3.举例模拟

示例：s = "ADOBECODEBANC", t = "ABC"

• t 统计：A:1，B:1，C:1，key_count=3
• right 不断右移： right 走到 C（下标 5），窗口ADOBEC，此时 count=3，满足条件； 进入 while 收缩 left，尝试缩小，记录长度 6； left 移动后，A 被移除，count 变为 2，停止收缩；
• 继续右移 right，直到再次凑齐 ABC； 后续找到窗口BANC，长度 4，是全局最小，最终返回"BANC"。

4.代码参考

class Solution { public: string minWindow(string s, string t) { int hash_1[128]={0}; int key_count=0;//关键字符个数 for(auto e:t) { if(hash_1[e]++==0) { key_count++; } } int hash_2[128]={0}; int begin=-1,len=INT_MAX; for(int left=0,right=0,count=0;right<s.size();right++) { char in=s[right]; if(++hash_2[in]==hash_1[in]) { count++; } while(key_count==count) { if(right-left+1<len) { len=right-left+1; begin=left; } char out=s[left]; if(hash_2[out]--==hash_1[out]) { count--; } left++; } } if(begin==-1) { return ""; } else { return s.substr(begin,len); } } };

5.复杂度

• 时间复杂度：（O(n+m))，(n=s.size(),m=t.size())。左右指针各自最多遍历 s 一遍，不会回头；哈希数组操作(O(1))。
• 空间复杂度：(O(1))，只用固定大小 128 的数组，常数空间，和输入长度无关。

五、总结

分类：不定长窗口、固定长度窗口，都用「频次哈希 + count 计数器」避免每次全表比对，提升效率

1. 水果成篮（不定长滑动窗口，最多 2 类）目标：最长子数组，元素种类≤2；right 扩，种类超 2 就收缩 left，记录最大值。
2. 找到字符串中所有字母异位词（定长滑动窗口）目标：和 p 等长、字符频次完全相同；窗口大小固定为 p 的长度，count 统计匹配字符数，count==p 长度即找到答案。
3. 串联所有单词的子串（定长滑动窗口，按单词块滑动）目标：连续凑齐 words 里全部单词；单词等长，枚举0~step-1起始偏移，每次 right/left 一跳一个单词，窗口固定总长 = 单词数量 × 单词长度。
4. 最小覆盖子串（不定长滑动窗口，全覆盖）目标：包含 t 全部字符及对应频次的最短子串；right 扩直到满足覆盖，然后循环收缩 left，不断更新最短窗口。

区分

不定长（水果成篮、最小覆盖子串）：窗口大小不固定，满足条件就收缩左边界；

1. 水果成篮：限制种类上限，求最长

2. 最小覆盖子串：要求全部覆盖，求最短

定长（异位词、串联单词）：窗口长度固定，只滑不主动缩，超长度就踢左边；

1. 字母异位词：按单个字符滑动

2. 串联单词：按整块单词滑动，需要多轮偏移