【优选算法】(实战体验滑动窗口的奇妙之旅)

🔥承渊政道：个人主页
❄️个人专栏: 《C语言基础语法知识》《数据结构与算法》《C++知识内容》《Linux系统知识》《算法刷题指南》《测评文章活动推广》
✨逆境不吐心中苦,顺境不忘来时路!✨🎬 博主简介:

在算法的世界里,“高效"永远是不变的追求,而优选算法的核心,就是在纷繁复杂的解题思路中,找到最简洁、最高效的解决方案.当我们面对数组、字符串的子区间问题时,常常会陷入暴力枚举的困境—双重循环带来的O(n²)时间复杂度,不仅会让代码运行效率低下,更会在数据量激增时陷入超时的僵局,成为算法进阶路上的"绊脚石”.而滑动窗口算法,正是破解这类问题的"神奇钥匙",它以其独特的动态窗口思想,将看似复杂的问题化繁为简,轻松实现时间复杂度从O(n²)到O(n)的跨越式优化,成为优选算法体系中不可或缺的核心工具之一.它就像一个可灵活移动的"观察框",通过双指针维护窗口的左右边界,在数据序列上有序滑动,动态调整窗口大小、更新窗口状态,无需重复计算,便能精准捕捉满足条件的子区间,这份"化繁为简"的魔力,正是它的奇妙之处所在.本次奇妙之旅,我们将跳出纯理论的框架,以实战为核心,手把手带你解锁滑动窗口的核心逻辑与应用技巧.无论你是刚接触算法的新手,还是想优化解题效率的进阶学习者,都能在这场实战之旅中,领略滑动窗口的独特魅力,掌握这一优选算法的实用技巧,让复杂的子区间问题迎刃而解.接下来,就让我们一起推开滑动窗口的大门,开启这场高效解题的奇妙探索吧!

目录

• 1.滑动窗口背景介绍
• 2.长度最小的子数组(OJ题)
• 3.无重复字符的最长子串(OJ题)
• 4.最大连续1的个数|||(OJ题)
• 5.将x减到0的最小操作数(OJ题)
• 6.水果成篮(OJ题)
• 7.找到字符串中所有字母异位词(OJ题)
• 8.串联所有单词的子串(OJ题)
• 9.最小覆盖子串(OJ题)

1.滑动窗口背景介绍

滑动窗口是双指针算法的经典分支,专门解决数组/字符串中连续子数组、子串的最优解问题.它的核心是:用两个指针界定一个动态的窗口,让窗口在序列上单向滑动,代替暴力枚举所有子序列,将时间复杂度从O(n²)优化到O(n)(线性时间).
窗口
由左指针left和右指针right界定的连续区间[left, right],窗口内的元素就是当前正在处理的连续子集.
滑动
两个指针只向右移动、绝不回退,窗口会像滑块一样在数组/字符串上从左滑到右,这是算法能做到线性时间的关键.
所有滑动窗口题目都遵循这个固定逻辑:
初始化
左指针left = 0,定义窗口状态变量(记录窗口内的和、字符计数、元素存在性等),定义结果变量.
扩张窗口
右指针 right 遍历整个序列,将当前元素加入窗口,更新窗口状态.
收缩窗口(动态窗口专属)
当窗口违反/满足题目条件时,移动左指针缩小窗口,同步更新窗口状态.
更新结果
在窗口滑动的过程中,记录最优解(最大/最小长度、和、值等).

2.长度最小的子数组(OJ题)

算法思路:解法一(暴力求解会超时)
从前往后枚举数组中的任意一个元素,把它当成起始位置.然后从这个起始位置开始,然后寻找一段最短的区间,使得这段区间的和大于等于目标值.
将所有元素作为起始位置所得的结果中,找到最小值即可.

核心代码

classSolution{public:intminSubArrayLen(int target, vector<int>& nums){//记录结果int ret = INT_MAX;int n = nums.size();//枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]//由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩//枚举开始位置for(int start =0; start < n; start++){int sum =0;//记录从这个位置开始的连续数组的和//寻找结束位置for(int end = start; end < n; end++){ sum += nums[end];//将当前位置加上if(sum >= target)//当这段区间内的和满⾜条件时{//更新结果，start 开头的最短区间已经找到 ret =min(ret, end - start +1);break;}}}//返回最后结果return ret == INT_MAX ?0: ret;}};

算法思路:解法二(滑动窗口)
由于此问题分析的对象是一段连续的区间,因此可以考虑滑动窗口的思想来解决这道题.
让滑动窗口满足:从 i 位置开始,窗口内所有元素的和小于 target(那么当窗口内元素之和第一次大于等于目标值的时候,就是 i 位置开始,满足条件的最小长度).
做法:将右端元素划入窗口中,统计出此时窗口内元素的和:

• 如果窗口内元素之和大于等于 target:更新结果,并且将左端元素划出去的同时继续判断是否满足条件并更新结果(因为左端元素可能很小,划出去之后依旧满足条件)
• 如果窗口内元素之和不满足条件:right++,另下一个元素进入窗口.

为何滑动窗口可以解决问题,并且时间复杂度更低?

• 这个窗口寻找的是:以当前窗口最左侧元素(记为 left1)为基准,符合条件的情况.也就是在这道题中,从 left1 开始,满足区间和 sum >= target 时的最右侧(记为 right1)能到哪里.
• 我们既然已经找到从 left1 开始的最优的区间,那么就可以大胆舍去 left1.但是如果继续像方法一一样,重新开始统计第二个元素(left2)往后的和,势必会有大量重复的计算(因为我们在求第一段区间的时候,已经算出很多元素的和了,这些和是可以在计算下次区间和的时候用上的).
• 此时,right1 的作用就体现出来了,我们只需将 left1 这个值从 sum 中剔除.从 right1 这个元素开始,往后找满足 left2 元素的区间(此时 right1 也有可能是满足的,因为 left1 可能很小.sum 剔除掉 left1 之后,依旧满足大于等于 target).这样我们就能省掉大量重复的计算.
• 这样我们不仅能解决问题,而且效率也会大大提升.

时间复杂度: 虽然代码是两层循环,但是我们的 left 指针和 right 指针都是不回退的,两者最多都往后移动 n 次.因此时间复杂度是 O(N).

核心代码

classSolution{public:intminSubArrayLen(int target, vector<int>& nums){int n = nums.size(), sum =0, len = INT_MAX;for(int left =0, right =0; right < n; right++){ sum += nums[right];//进窗⼝while(sum >= target)//判断{ len =min(len, right - left +1);//更新结果 sum -= nums[left++];//出窗⼝}}return len == INT_MAX ?0: len;}};

完整测试代码

#include<iostream>#include<vector>#include<algorithm>usingnamespace std;classSolution{public:intminSubArrayLen(int target, vector<int>& nums){int n = nums.size(), sum =0, len = INT_MAX;for(int left =0, right =0; right < n; right++){ sum += nums[right];// 右指针扩窗口while(sum >= target)// 满足条件，收缩左指针{ len =min(len, right - left +1);// 更新最小长度 sum -= nums[left++];// 左指针缩窗口}}//无满足条件的子数组返回0，否则返回最小长度return len == INT_MAX ?0: len;}};intmain(){ Solution sol;int target1 =7; vector<int> nums1 ={2,3,1,2,4,3}; cout <<"{2, 3, 1, 2, 4, 3}"<< sol.minSubArrayLen(target1, nums1)<< endl;int target2 =11; vector<int> nums2 ={1,1,1,1,1,1,1,1}; cout <<"{1,1,1,1,1,1,1,1}"<< sol.minSubArrayLen(target2, nums2)<< endl;int target3 =4; vector<int> nums3 ={1,4,4}; cout <<"{1,4,4}"<< sol.minSubArrayLen(target3, nums3)<< endl;return0;}

3.无重复字符的最长子串(OJ题)

算法思路:解法一(暴力求解➡️不会超时,可以通过)
枚举从每一个位置开始往后,无重复字符的子串可以到达什么位置.找出其中长度最大的即可.
在往后寻找无重复子串能到达的位置时,可以利用哈希表统计出字符出现的频次,来判断什么时候子串出现了重复元素.
核心代码

classSolution{public:intlengthOfLongestSubstring(string s){int ret =0;//记录结果int n = s.length();// 1.枚举从不同位置开始的最⻓重复⼦串//枚举起始位置for(int i =0; i < n; i++){//创建⼀个哈希表，统计频次int hash[128]={0};//寻找结束为⽌for(int j = i; j < n; j++){ hash[s[j]]++;//统计字符出现的频次if(hash[s[j]]>1)//如果出现重复的break;//如果没有重复，就更新 ret ret =max(ret, j - i +1);}}// 2. 返回结果return ret;}};

算法思路:解法二(滑动窗口)
研究的对象依旧是一段连续的区间,因此继续使用滑动窗口思想来优化.
让滑动窗口满足:窗口内所有元素都是不重复的.
做法:右端元素 ch 进入窗口的时候,哈希表统计这个字符的频次:

• 如果这个字符出现的频次超过 1,说明窗口内有重复元素,那么就从左侧开始划出窗口,直到 ch 这个元素的频次变为 1,然后再更新结果.

如果没有超过 1,说明当前窗口没有重复元素,可以直接更新结果

核心代码

classSolution{public:intlengthOfLongestSubstring(string s){int hash[128]={0};// 使⽤数组来模拟哈希表int left =0, right =0, n = s.size();int ret =0;while(right < n){ hash[s[right]]++;//进⼊窗⼝while(hash[s[right]]>1)//判断 hash[s[left++]]--;//出窗⼝ ret =max(ret, right - left +1);//更新结果 right++;//让下⼀个元素进⼊窗⼝}return ret;}};

完整测试代码

// 必备头文件#include<iostream>#include<string>#include<algorithm>usingnamespace std;classSolution{public:intlengthOfLongestSubstring(string s){int hash[128]={0};//数组模拟哈希表，记录ASCII字符出现次数int left =0, right =0, n = s.size();int ret =0;//存储最长无重复子串长度while(right < n){ hash[s[right]]++;//右指针字符进入窗口while(hash[s[right]]>1)//出现重复字符，收缩窗口 hash[s[left++]]--;//左指针字符移出窗口 ret =max(ret, right - left +1);//更新最长长度 right++;//右指针右移，扩张窗口}return ret;}};intmain(){ Solution sol; string s1 ="abcabcbb"; cout <<"abcabcbb："<< sol.lengthOfLongestSubstring(s1)<< endl; string s2 ="bbbbb"; cout <<"bbbbb："<< sol.lengthOfLongestSubstring(s2)<< endl; string s3 ="pwwkew"; cout <<"pwwkew："<< sol.lengthOfLongestSubstring(s3)<< endl; string s4 =""; cout <<""<< sol.lengthOfLongestSubstring(s4)<< endl; string s5 =" "; cout <<""<< sol.lengthOfLongestSubstring(s5)<< endl;return0;}

4.最大连续1的个数|||(OJ题)

算法思路:解法(滑动窗口)
不要去想怎么翻转,不要把问题想的很复杂,这道题的结果无非就是一段连续的 1 中间塞了 k 个 0 嘛.因此,我们可以把问题转化成:求数组中一段最长的连续区间,要求这段区间内 0 的个数不超过 k 个.
算法流程
①初始化一个大小为 2 的数组就可以当做哈希表 hash 了；初始化一些变量 left = 0，right = 0，ret = 0；
②当 right 小于数组大小的时候,一直下列循环:
(1)让当前元素进入窗口,顺便统计到哈希表中;
(2)检查 0 的个数是否超标:如果超标,依次让左侧元素滑出窗口,顺便更新哈希表的值,直到 0 的个数恢复正常;
(3)程序到这里,说明窗口内元素是符合要求的,更新结果;
(4)right++,处理下一个元素;
③循环结束后,ret 存的就是最终结果.

核心代码

classSolution{public:intlongestOnes(vector<int>& nums,int k){int ret =0;for(int left =0, right =0, zero =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;}};

完整测试代码

#include<iostream>#include<vector>#include<algorithm>usingnamespace std;classSolution{public:intlongestOnes(vector<int>& nums,int k){int ret =0;for(int left =0, right =0, zero =0; right < nums.size(); right++){if(nums[right]==0) zero++;// 进窗口：右指针元素加入，统计0的个数while(zero > k)// 判断：0超标，收缩窗口if(nums[left++]==0) zero--;// 出窗口：左指针右移，减少0的个数 ret =max(ret, right - left +1);// 更新最大窗口长度}return ret;}};intmain(){ Solution sol; vector<int> nums1 ={1,1,1,0,0,0,1,1,1,1,0};int k1 =2; cout <<"{1,1,1,0,0,0,1,1,1,1,0}"<< sol.longestOnes(nums1, k1)<<" （预期：6）"<< endl; vector<int> nums2 ={0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1};int k2 =3; cout <<"{0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1}"<< sol.longestOnes(nums2, k2)<<" （预期：10）"<< endl; vector<int> nums3 ={1,0,1,1,0};int k3 =1; cout <<"{1,0,1,1,0}"<< sol.longestOnes(nums3, k3)<<" （预期：4）"<< endl; vector<int> nums4 ={1,1,1,1};int k4 =2; cout <<"{1,1,1,1}"<< sol.longestOnes(nums4, k4)<<" （预期：4）"<< endl; vector<int> nums5 ={0,0,0,0};int k5 =3; cout <<"{0,0,0,0}"<< sol.longestOnes(nums5, k5)<<" （预期：3）"<< endl;return0;}

5.将x减到0的最小操作数(OJ题)

算法思路:解法(滑动窗口)
题目要求的是数组左端+右端两段连续的、和为 x 的最短数组,信息量稍微多一些,不易理清思路;我们可以转化成求数组内一段连续的、和为 sum(nums) - x 的最长数组.此时,就是熟悉的滑动窗口问题了.
算法流程
①转化问题:求 target = sum(nums) - x.如果 target < 0,问题无解;
②初始化左右指针 l = 0,r = 0(滑动窗口区间表示为 [l, r),左右区间是否开闭很重要,必须设定与代码一致),记录当前滑动窗口内数组和的变量 sum = 0,记录当前满足条件数组的最大区间长度 maxLen = -1;
③当 r 小于等于数组长度时,一直循环:
(1)如果 sum < target,右移右指针,直至变量和大于等于 target,或右指针已经移到头;
(2)如果 sum > target,右移左指针,直至变量和小于等于 target,或左指针已经移到头;
(3)如果经过前两步的左右移动使得 sum == target,维护满足条件数组的最大长度,并让下个元素进入窗口;
④循环结束后,如果 maxLen 的值有意义,则计算结果返回;否则,返回 -1.

核心代码

classSolution{public:intminOperations(vector<int>& nums,int x){int sum =0;for(int a : nums) sum += a;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 ret;elsereturn nums.size()- ret;}};

完整测试代码

#include<iostream>#include<vector>#include<algorithm>usingnamespace std;classSolution{public:intminOperations(vector<int>& nums,int x){int sum =0;for(int a : nums) sum += a;int target = sum - x;//细节：数组总和小于x，无法减到0if(target <0)return-1;int ret =-1;//滑动窗口寻找和为target的最长连续子数组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);}//无结果返回-1，否则总长度-最长子数组长度=最小操作数return ret ==-1?-1: nums.size()- ret;}};intmain(){ Solution sol; vector<int> nums1 ={1,1,4,2,3};int x1 =5; cout <<"{1,1,4,2,3}"<< sol.minOperations(nums1, x1)<<" （预期：2）"<< endl; vector<int> nums2 ={5,6,7,8,9};int x2 =4; cout <<"{5,6,7,8,9}"<< sol.minOperations(nums2, x2)<<" （预期：-1）"<< endl; vector<int> nums3 ={3,2,20,1,1,3};int x3 =10; cout <<"{3,2,20,1,1,3}"<< sol.minOperations(nums3, x3)<<" （预期：5）"<< endl; vector<int> nums4 ={1,2,3};int x4 =6; cout <<"{1,2,3}"<< sol.minOperations(nums4, x4)<<" （预期：3）"<< endl; vector<int> nums5 ={2,4,6};int x5 =13; cout <<"{2,4,6}"<< sol.minOperations(nums5, x5)<<" （预期：-1）"<< endl;return0;}

6.水果成篮(OJ题)

算法思路:解法(滑动窗口)
研究的对象是一段连续的区间,可以使用滑动窗口思想来解决问题.
让滑动窗口满足:窗口内水果的种类只有两种.
做法
右端水果进入窗口的时候,用哈希表统计这个水果的频次.这个水果进来后,判断哈希表的大小:
如果大小超过2:说明窗口内水果种类超过了两种.那么就从左侧开始依次将水果划出窗口,直到哈希表的大小小于等于2,然后更新结果;
如果没有超过 2,说明当前窗口内水果的种类不超过两种,直接更新结果 ret.
算法流程
①初始化哈希表 hash 来统计窗口内水果的种类和数量；
②初始化变量:左右指针 left = 0,right = 0,记录结果的变量 ret = 0;
③当 right 小于数组大小的时候,一直执行下列循环:
(1)将当前水果放入哈希表中;
(2)判断当前水果进来后,哈希表的大小:
• 如果超过2：
◦ 将左侧元素滑出窗口,并且在哈希表中将该元素的频次减一;
◦ 如果这个元素的频次减一之后变成了0,就把该元素从哈希表中删除;
◦ 重复上述两个过程,直到哈希表中的大小不超过2;
(3)更新结果 ret;
(4)right++,让下一个元素进入窗口;
④循环结束后,ret 存的就是最终结果.

核心代码

classSolution{public:inttotalFruit(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;}};//可以用数组模拟一下哈希表从而优化一下时间效率classSolution{public:inttotalFruit(vector<int>& f){int hash[100001]={0};//统计窗⼝内出现了多少种⽔果int ret =0;for(int left =0, right =0, kinds =0; right < f.size(); right++){if(hash[f[right]]==0) kinds++;//维护⽔果的种类 hash[f[right]]++;//进窗⼝while(kinds >2)//判断{//出窗⼝ hash[f[left]]--;if(hash[f[left]]==0) kinds--; left++;} ret =max(ret, right - left +1);}return ret;}};

完整测试代码

#include<iostream>#include<vector>#include<unordered_map>#include<algorithm>usingnamespace std;classSolution{public:inttotalFruit(vector<int>& f){ unordered_map<int,int> hash;//哈希表：key=水果种类，value=窗口内数量int ret =0;//记录最大采摘数//滑动窗口双指针for(int left =0, right =0; right < f.size(); right++){ hash[f[right]]++;//进窗口：右指针水果加入，计数+1//窗口内水果种类超过2种，收缩左指针while(hash.size()>2){ hash[f[left]]--;//出窗口：左指针水果计数-1//计数为0，删除该种类（保证hash.size()准确）if(hash[f[left]]==0) hash.erase(f[left]); left++;}//更新最长合法窗口长度 ret =max(ret, right - left +1);}return ret;}};intmain(){ Solution sol; vector<int> nums1 ={1,2,1}; cout <<"{1,2,1}"<< sol.totalFruit(nums1)<<" （预期:3）"<< endl; vector<int> nums2 ={0,1,2,2}; cout <<"{0,1,2,2}"<< sol.totalFruit(nums2)<<" （预期:3）"<< endl; vector<int> nums3 ={1,2,3,2,2}; cout <<"{1,2,3,2,2}"<< sol.totalFruit(nums3)<<" （预期:4）"<< endl; vector<int> nums4 ={3,3,3,3}; cout <<"{3,3,3,3}"<< sol.totalFruit(nums4)<<" （预期:4）"<< endl; vector<int> nums5 ={0,1,0,1,0}; cout <<"{0,1,0,1,0}"<< sol.totalFruit(nums5)<<" （预期:5）"<< endl;return0;}

7.找到字符串中所有字母异位词(OJ题)

算法思路:解法(滑动窗口 + 哈希表)
因为字符串 p 的异位词的长度一定与字符串 p 的长度相同,所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口,并在滑动中维护窗口中每种字母的数量;
当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时,则说明当前窗口为字符串 p 的异位词;
因此可以用两个大小为 26 的数组来模拟哈希表,一个来保存 s 中的子串每个字符出现的个数,另一个来保存 p 中每一个字符出现的个数.这样就能判断两个串是否是异位词.

核心代码

classSolution{public: vector<int>findAnagrams(string s, string p){ vector<int> ret;int hash1[26]={0};//统计字符串 p 中每个字符出现的个数for(auto ch : p) hash1[ch -'a']++;int hash2[26]={0};//统计窗⼝⾥⾯的每⼀个字符出现的个数int m = p.size();for(int left =0, right =0, count =0; right < s.size(); right++){char in = s[right];//进窗⼝ + 维护 countif(++hash2[in -'a']<= hash1[in -'a']) count++;if(right - left +1> m)//判断{char out = s[left++];//出窗⼝ + 维护 countif(hash2[out -'a']--<= hash1[out -'a']) count--;}//更新结果if(count == m) ret.push_back(left);}return ret;}};

完整测试代码

#include<iostream>#include<vector>#include<string>usingnamespace std;classSolution{public: vector<int>findAnagrams(string s, string p){ vector<int> ret;int hash1[26]={0};//统计字符串 p 中每个字符出现的个数for(auto ch : p) hash1[ch -'a']++;int hash2[26]={0};//统计窗口里面的每一个字符出现的个数int m = p.size();for(int left =0, right =0, count =0; right < s.size(); right++){char in = s[right];//进窗口 + 维护 countif(++hash2[in -'a']<= hash1[in -'a']) count++;if(right - left +1> m)//判断：窗口长度超过p的长度，收缩{char out = s[left++];//出窗口 + 维护 countif(hash2[out -'a']--<= hash1[out -'a']) count--;}//更新结果：count等于p长度，说明窗口是p的异位词if(count == m) ret.push_back(left);}return ret;}};voidprintResult(vector<int>& res){ cout <<"[";for(int i =0; i < res.size(); i++){if(i >0) cout <<","; cout << res[i];} cout <<"]"<< endl;}intmain(){ Solution sol; string s1 ="cbaebabacd"; string p1 ="abc"; vector<int> res1 = sol.findAnagrams(s1, p1); cout <<"测试用例1结果：";printResult(res1);//预期：[0,6] cout <<"（预期：[0,6]）"<< endl; string s2 ="abab"; string p2 ="ab"; vector<int> res2 = sol.findAnagrams(s2, p2); cout <<"测试用例2结果：";printResult(res2);//预期：[0,1,2] cout <<"（预期：[0,1,2]）"<< endl; string s3 ="a"; string p3 ="ab"; vector<int> res3 = sol.findAnagrams(s3, p3); cout <<"测试用例3结果：";printResult(res3);//预期：[] cout <<"（预期：[]）"<< endl; string s4 ="abc"; string p4 ="abc"; vector<int> res4 = sol.findAnagrams(s4, p4); cout <<"测试用例4结果：";printResult(res4);//预期：[0] cout <<"（预期：[0]）"<< endl;return0;}

8.串联所有单词的子串(OJ题)

算法思路:解法一(暴力解法)
如果我们把每一个单词看成一个一个字母,问题就变成了找到字符串中所有的字母异位词.无非就是之前处理的对象是一个一个的字符,我们这里处理的对象是一个一个的单词.

核心代码

classSolution{public: vector<int>findSubstring(string s, vector<string>& words){ vector<int> ret; unordered_map<string,int> hash1;//保存 words ⾥⾯所有单词的频次for(auto& s : words) hash1[s]++;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 + len <= s.size(); right += len){//进窗⼝ + 维护count string in = s.substr(right, len); hash2[in]++;if(hash1.count(in)&& hash2[in]<= hash1[in]) count++;//判断if(right - left +1> len * m){//出窗⼝ + 维护 count string out = s.substr(left, len);if(hash1.count(out)&& hash2[out]<= hash1[out]) count--; hash2[out]--; left += len;}//更新结果if(count == m) ret.push_back(left);}}return ret;}};

完整测试代码

#include<iostream>#include<vector>#include<string>#include<unordered_map>usingnamespace std;classSolution{public: vector<int>findSubstring(string s, vector<string>& words){ vector<int> ret; unordered_map<string,int> hash1;//保存 words 里面所有单词的频次for(auto& s : words) hash1[s]++;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 + len <= s.size(); right += len){//进窗口 + 维护count string in = s.substr(right, len); hash2[in]++;if(hash1.count(in)&& hash2[in]<= hash1[in]) count++;// 判断if(right - left +1> len * m){//出窗口 + 维护count string out = s.substr(left, len);if(hash1.count(out)&& hash2[out]<= hash1[out]) count--; hash2[out]--; left += len;}//更新结果if(count == m) ret.push_back(left);}}return ret;}};voidprintResult(vector<int>& res){ cout <<"[";for(int i =0; i < res.size(); i++){if(i >0) cout <<","; cout << res[i];} cout <<"]"<< endl;}intmain(){ Solution sol; string s1 ="barfoothefoobarman"; vector<string> words1 ={"foo","bar"}; vector<int> res1 = sol.findSubstring(s1, words1); cout <<"测试用例1结果：";printResult(res1);// 预期：[0,9] cout <<"（预期：[0,9]）"<< endl; string s2 ="wordgoodgoodgoodbestword"; vector<string> words2 ={"word","good","best","word"}; vector<int> res2 = sol.findSubstring(s2, words2); cout <<"测试用例2结果：";printResult(res2);// 预期：[] cout <<"（预期：[]）"<< endl; string s3 ="barbarfoo"; vector<string> words3 ={"bar","foo"}; vector<int> res3 = sol.findSubstring(s3, words3); cout <<"测试用例3结果：";printResult(res3);// 预期：[3] cout <<"（预期：[3]）"<< endl; string s4 ="fooba"; vector<string> words4 ={"foo","bar"}; vector<int> res4 = sol.findSubstring(s4, words4); cout <<"测试用例4结果：";printResult(res4);// 预期：[] cout <<"（预期：[]）"<< endl;return0;}

9.最小覆盖子串(OJ题)

算法思路:解法(滑动窗口+哈希表)
研究对象是连续的区间,因此可以尝试使用滑动窗口的思想来解决.
如何判断当前窗口内的所有字符是符合要求的呢？
我们可以使用两个哈希表,其中一个将目标串的信息统计起来,另一个哈希表动态的维护窗口内字符串的信息.
当动态哈希表中包含目标串中所有的字符,并且对应的个数都不小于目标串的哈希表中各个字符的个数,那么当前的窗口就是一种可行的方案.
算法流程
①定义两个全局的哈希表:1号哈希表 hash1 用来记录子串的信息,2号哈希表 hash2 用来记录目标串 t 的信息;
②实现一个接口函数,判断当前窗口是否满足要求:
(1)遍历两个哈希表中对应位置的元素:
如果 t 中某个字符的数量大于窗口中字符的数量,也就是 2 号哈希表某个位置大于 1 号哈希表,说明不匹配,返回 false;
如果全都匹配,返回 true.
主函数中
①先将 t 的信息放入 2 号哈希表中;
②初始化一些变量:左右指针:left = 0,right = 0;目标子串的长度:len = INT_MAX;目标子串的起始位置:retleft;(通过目标子串的起始位置和长度,我们就能找到结果）
③当 right 小于字符串 s 的长度时,一直下列循环:
(1)将当前遍历到的元素扔进 1 号哈希表中;
(2)检测当前窗口是否满足条件:
如果满足条件:
◦ 判断当前窗口是否变小.如果变小:更新长度 len,以及字符串的起始位置 retleft;
◦ 判断完毕后,将左侧元素滑出窗口,顺便更新 1 号哈希表;
◦ 重复上面两个过程,直到窗口不满足条件;
(3)right++,遍历下一个元素;
④判断 len 的长度是否等于 INT_MAX:
(1)如果相等,说明没有匹配,返回空串;
(2)如果不相等,说明匹配,返回 s 中从 retleft 位置往后 len 长度的字符串.

核心代码

classSolution{public: string minWindow(string s, string t){int hash1[128]={0};//统计字符串t中每⼀个字符的频次int kinds =0;//统计有效字符有多少种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++;//进窗⼝ + 维护 countwhile(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"";elsereturn s.substr(begin, minlen);}};

完整测试代码

#include<iostream>#include<string>#include<climits>usingnamespace std;classSolution{public: string minWindow(string s, string t){int hash1[128]={0};//统计字符串t中每一个字符的频次int kinds =0;//统计有效字符有多少种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++;//进窗口 + 维护countwhile(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"";elsereturn s.substr(begin, minlen);}};intmain(){ Solution sol; string s1 ="ADOBECODEBANC"; string t1 ="ABC"; cout <<"测试用例1结果："<< sol.minWindow(s1, t1)<<" （预期：BANC）"<< endl; string s2 ="a"; string t2 ="a"; cout <<"测试用例2结果："<< sol.minWindow(s2, t2)<<" （预期：a）"<< endl; string s3 ="a"; string t3 ="aa"; cout <<"测试用例3结果：\""<< sol.minWindow(s3, t3)<<"\" （预期：空串）"<< endl; string s4 ="aa"; string t4 ="aa"; cout <<"测试用例4结果："<< sol.minWindow(s4, t4)<<" （预期：aa）"<< endl;return0;}

🚀真正的勇者不是流泪的人,而是含泪奔跑的人!

敬请期待下一篇文章内容:【优选算法】(实战感悟二分查找算法的思想原理)

每日心灵鸡汤:我依旧待人真诚,但不再给予厚望!
我从不后悔对任何人好,哪怕是看错人,哪怕是撞南墙,我愿意为我的选择买单,也不后悔我的任何决定,只是因为我很好,樱花树下站谁都美,我的爱给谁都热烈,我爱谁谁才会特别.
不将别人的给予当成理所当然,更不怀疑自己的善良和真诚,应当反省的从来都是自己的眼光和见识.人性如此幽深复杂,千帆过尽,我变得什么都能理解,每次的真诚让我觉得踏实.所以在失去的时候,有遗憾的不该是我.