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、rightright 不断向右扩张窗口把水果加入哈希数组统计数量count记录当前窗口内水果种类数一旦count2说明窗口非法移动 left 收缩窗口直到种类 ≤2每次窗口合法后计算窗口长度更新最大长度rethash 数组充当频次表hash [x] 窗口内 x 出现次数3.举例模拟样例f [1,2,1,2,3]初始left0, count0, ret0, hash 全 0表格rightf[right]hash 变化countcount2?left 移动窗口 [left,right]长度ret01hash[1]11否-[0,0]1112hash[2]12否-[0,1]2221hash[1]22否-[0,2]3332hash[2]22否-[0,3]4443hash[3]13是收缩hash [1]-- → hash [1]1不为 0count 不变left1hash [2]-- → hash [2]1不为 0count 不变left2hash[1]-- → hash[1]0count2left3[3,4]24最终返回 44.代码参考class Solution { public: int totalFruit(vectorint f) { int hash[100001]{0}; int ret0; for(int left0,right0,count0;rightf.size();right) { //更新count if(hash[f[right]]0) count; //进窗口 hash[f[right]]; while(count2) { hash[f[left]]--; //出窗口 if(hash[f[left]]0) count--; left; } //更新结果 retmax(ret,right-left1); } return ret; } };5.复杂度时间复杂度O (n)left 和 right 各自最多从 0 走到 n-1每个元素最多入窗口一次、出窗口一次总操作线性。空间复杂度O (M)M100001是 hash 数组的固定大小如果值域很大一般改用 unordered_map空间是 O (1)最多存 2 个 key。二、找到字符串中所有字母异位词1.题目2.核心思路本题求解字符串s中所有p的字母异位词起始下标采用固定长度滑动窗口 字符频次数组 有效字符计数器 count。数组hash_1[26]统计模式串p中每个小写字母的出现频次数组hash_2[26]维护滑动窗口[left, right]内部各字母的频次count代表窗口内满足「当前频次 ≤ p 中对应字母频次」的有效字符数量右指针向右扩张窗口进窗口先将当前字符频次hash_2自增若增加后的值小于等于hash_1说明该字符是有效匹配字符count当窗口长度大于p的长度m窗口需要收缩取出左边界字符先判断当前频次是否满足有效条件满足则count--再将频次减 1左指针右移当count m说明窗口内有效字符总数等于模式串长度当前窗口就是p的异位词记录窗口左端点left。异位词定义字符种类、每种字符出现次数完全一致字符顺序不同。3.举例模拟测试样例s cbaebabacdp abcm 3初始化hash_1[a]1,hash_1[b]1,hash_1[c]1其余为 0left0,count0hash_2全部置 0表格rights[right]hash_2count窗口长度 3out判断 hash2 [out] ≤ hash1 [out]counthash2[out]--count3ret0chash2[c]11否----❌-1bhash2[b]12否----❌-2ahash2[a]13否----✅[0]3ehash2[e]13是c1 ≤ 1 ✔2hash2[c]0❌-4bhash2[b]22是b2 ≤ 1 ✖2hash2[b]1❌-5ahash2[a]22是a2 ≤ 1 ✖2hash2[a]1❌-6bhash2[b]22是e1 ≤ 0 ✖2hash2[e]0✅[0,6]7ahash2[a]22是b2 ≤ 1 ✖2hash2[b]1❌-8chash2[c]13是a2 ≤ 1 ✖3hash2[a]1✅[0,6]9dhash2[d]13是b1 ≤ 1 ✔2hash2[b]0❌-最终输出[0,6]4.代码参考class Solution { public: vectorint findAnagrams(string s, string p) { int mp.size(); int hash_1[26]{0}; for(auto e: p) { hash_1[e-a]; } int hash_2[26]{0}; vectorint ret; for(int left0,right0,count0;rights.size();right) { char ins[right]; if(hash_2[in-a] hash_1[in-a]) { count; } if(right-left1m) { char outs[left]; if(hash_2[out-a] hash_1[out-a]) { count--; } hash_2[out-a]--; left; } if(countm) { ret.push_back(left); } } return ret; } };5.复杂度设 n s.size(), m p.size()时间复杂度(O(nm)) 遍历 p 统计频次(O(m))滑动窗口只遍历 s 一遍每个元素只进窗口一次、出窗口一次无内层循环(O(n))空间复杂度(O(1)) 只固定开辟大小为 26 的数组和输入规模无关返回答案数组不计入算法额外空间开销。三、串联所有单词的子串1.题目2.核心思路前提words 里所有单词长度相等记为step单词总数量n目标窗口总字符长度 step * n先用hash_1统计 words 中每个单词需要出现多少次作为标准对照。外层循环for(int i0;istep;i)枚举起始偏移量 i。 因为我们滑动窗口每次按整块单词step个字符移动不能逐字符滑一共有0 ~ step-1共step种不同的切分对齐方式必须分开跑滑动窗口防止漏掉答案。对每一个偏移 i独立开启一套滑动窗口left窗口左边界right窗口右边界每次right step一次读入一整个单词hash_2维护当前窗口内单词频次count窗口内符合要求次数不超过 hash_1的单词数量count n代表窗口匹配成功进窗口读取right位置单词更新hash_2如果这个单词是目标单词且新增后次数没有超标count出窗口如果当前窗口总长度 step*n说明窗口过长弹出最左侧单词。如果被弹出单词在弹出前是合规的count--更新频次、左边界右移每次调整完窗口判断count n满足就把left加入结果数组。优化点不用每次比较两张哈希表用 count 变量 O (1) 判断是否匹配成功。3.举例模拟样例s barfoothefoobarman,words {foo,bar}step 3n 2目标窗口总长 6hash_1: {foo:1, bar:1}外层 i 从 0 开始偏移 0 初始化left0, right0, count0, hash_2为空right0 in barhash_2 [bar]111 → count1 窗口长度 0-011 ≤6不收缩 count≠2无结果right3 in foohash_2 [foo]111 → count2 窗口长度 3-014 ≤6不收缩 count2 → left0 存入答案 ret[0]right6 in the不在 hash_1count 不变 窗口长度 6-017 6 → 触发出窗口 outbarhash_2 [bar]1 ≤1 → count1hash_2 [bar]-- →0left3 count≠2right9 infoohash_2 [foo]2 hash_1 [foo]1 → count 不变 窗口长度 9-3176弹出 outfoohash_2 [foo]2弹出前 1count 不变hash_2 [foo]--1left6right12 inbarhash_2 [bar]1 ≤1 → count2 count2 → left9 存入答案 ret[0,9] 后面继续循环…… i1、i2 两个偏移继续单独跑滑动窗口这组样例没有更多答案。4.代码参考class Solution { public: vectorint findSubstring(string s, vectorstring words) { unordered_mapstring,int hash_1; for(auto e:words) { hash_1[e]; } vectorint ret; int stepwords[0].size(),nwords.size(); for(int i0;istep;i) { unordered_mapstring,int hash_2; for(int lefti,righti,count0;rightsteps.size();rightstep) { //进窗口 string ins.substr(right,step); hash_2[in]; if(hash_1.count(in) hash_2[in]hash_1[in]) { count; } //出窗口 if(right-left1step*n) { string outs.substr(left,step); if(hash_1.count(out) hash_2[out]hash_1[out]) { count--; } hash_2[out]--; leftstep; } //更新结果 if(countn) { ret.push_back(left); } } } return ret; } };5.复杂度设s长度Sstep单词长度nwords 单词数量时间复杂度O(step* S) 外层循环执行step次每一轮内层滑动窗口中right只会向前移动每个字符最多被访问一次哈希表操作平均 O (1)空间复杂度O(n两张哈希表最多存储 words 里所有单词最多 n 个键值对。四、最小覆盖子串1.题目2.核心思路这是不定长滑动窗口双指针经典题在s中找包含t全部字符含对应频次的最短子串。用两个数组hash_1、hash_2分别统计t的字符频次、窗口[left, right]内字符频次key_countt 中不同字符的种类数count窗口内已经满足频次要求的字符种类右指针right不断向右扩大窗口加入字符当某字符窗口频次等于 t 的频次时count当count key_count说明当前窗口已经覆盖 t 全部字符进入收缩阶段尝试移动左指针left缩小窗口更新最短子串如果被移出的字符移出前刚好等于 t 需要的频次count--退出收缩循环全程记录最优窗口起点begin和长度len最后截取返回。重点不是 “出现过” 就行要满足数量比如tAABC窗口里 A 必须≥2、B≥1、C≥1。3.举例模拟示例s ADOBECODEBANC, t ABCt 统计A:1B:1C:1key_count3right 不断右移 right 走到 C下标 5窗口ADOBEC此时 count3满足条件 进入 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_count0;//关键字符个数 for(auto e:t) { if(hash_1[e]0) { key_count; } } int hash_2[128]{0}; int begin-1,lenINT_MAX; for(int left0,right0,count0;rights.size();right) { char ins[right]; if(hash_2[in]hash_1[in]) { count; } while(key_countcount) { if(right-left1len) { lenright-left1; beginleft; } char outs[left]; if(hash_2[out]--hash_1[out]) { count--; } left; } } if(begin-1) { return ; } else { return s.substr(begin,len); } } };5.复杂度时间复杂度O(nm))(ns.size(),mt.size())。左右指针各自最多遍历 s 一遍不会回头哈希数组操作(O(1))。空间复杂度(O(1))只用固定大小 128 的数组常数空间和输入长度无关。五、总结分类不定长窗口、固定长度窗口都用「频次哈希 count 计数器」避免每次全表比对提升效率水果成篮不定长滑动窗口最多 2 类目标最长子数组元素种类≤2right 扩种类超 2 就收缩 left记录最大值。找到字符串中所有字母异位词定长滑动窗口目标和 p 等长、字符频次完全相同窗口大小固定为 p 的长度count 统计匹配字符数countp 长度即找到答案。串联所有单词的子串定长滑动窗口按单词块滑动目标连续凑齐 words 里全部单词单词等长枚举0~step-1起始偏移每次 right/left 一跳一个单词窗口固定总长 单词数量 × 单词长度。最小覆盖子串不定长滑动窗口全覆盖目标包含 t 全部字符及对应频次的最短子串right 扩直到满足覆盖然后循环收缩 left不断更新最短窗口。区分不定长水果成篮、最小覆盖子串窗口大小不固定满足条件就收缩左边界1. 水果成篮限制种类上限求最长2. 最小覆盖子串要求全部覆盖求最短定长异位词、串联单词窗口长度固定只滑不主动缩超长度就踢左边1. 字母异位词按单个字符滑动2. 串联单词按整块单词滑动需要多轮偏移