【优选算法】滑动窗口专项：1.长度最小的子数组 2.无重复最长子串

🔥小龙报：个人主页
🎬作者简介：C++研发，嵌入式，机器人，AI等方向学习者
❄️个人专栏：《优选算法》
✨永远相信美好的事情即将发生

前言

滑动窗口是数组、字符串高频考点，依靠同向双指针规避暴力枚举的双层循环，将时间复杂度优化至 O (n)。本文选取两道经典例题拆解思路：和大于目标值的最短子数组、无重复最长子串。分别讲解纯滑动窗口、哈希数组搭配窗口的两种模板，清晰拆解进窗、校验、出窗流程，附上可直接提交的 C++ 完整代码，帮助快速掌握窗口边界控制逻辑，适配各类同类型刷题场景。

一、长度最小的子数组

1.1题目

链接：长度最小的子数组

1.2 算法原理

核心思想:单调性同向双指针

我们「暴力枚举」的过程中，固定⼀个起点位置left，然后之后right向后遍历时。当right第一次扫描到⼀个位置，使[left,right]这个区间大于等于target，此时我们会发现：
• right 无需再向后遍历，因为继续向后走区间窗口也是「不合法」的；
• left向后移动一格之后，right 指针也不用回退，因为我们已经维护出来[left,right]区间的信息，并且以left + 1 为起点的最优解一定不会比left为起点的好
当我们发现暴力枚举的「两个指针不回退」时，就可以用「滑动窗口」优化：
（1）进窗口：right 位置元素记录到sum中；
（2）判断：当sum >= target之后，窗口内子串合法,并更新结果；
（3）出窗口：让left 所指位置的元素在sum中的减去nums[l]；

1.3 代码

classSolution{public:intminSubArrayLen(inttarget,vector<int>&nums){intl=0,r=0,n=nums.size();intsum=0,len=1e6+10;while(r<n){//进窗口sum+=nums[r];//判断while(sum>=target){len=min(len,r-l+1);sum-=nums[l++];//出窗口}r++;}returnlen==1e6+10?0:len;}};

时间复杂度: O(n)

二、无重复最长子串

2.1 题目

链接：无重复最长子串

2.2 算法原理

核心思想：哈希表 + 同向双指针
定义一个数组h记录当前窗口内统计到字符种类
（1）进窗口：right位置元素记录到统计次数的哈希表中，如果次数是0 变1 ，说明窗口内多了「⼀种」字符，记录⼀下；
（2）判断：当窗口内字符种类大于1时，窗口不合法，right 停止右移（寻找到当前情况的最优解），接下来需要出窗口；
（3）出窗口：让left 所指位置的元素在哈希表中的次数减一，如果次数是1 变0 ，说明窗口内少了「一种」字符，记录一下；
（4）更新结果：在判断未成立时，窗口合法，此时更新窗口大小

2.3 代码

classSolution{public:intlengthOfLongestSubstring(string s){inth[128]={0};//用数组模拟哈希表intl=0,r=0,n=s.size();intret=0;while(r<n){h[s[r]]++;//进窗口while(h[s[r]]>1)//判断 + 出窗口（此时窗口非法）h[s[l++]]--;ret=max(ret,r-l+1);//更新合法窗口的结果r++;}returnret;}};

时间复杂度: O（N）

总结与每日励志

✨两道例题完整覆盖滑动窗口核心逻辑，关键在于利用单调性保证指针只前进不回退，搭配数组哈希快速统计字符频次。刷题时牢记三步模板：右指针扩张窗口，满足条件就收缩左边界，实时更新最优答案。算法学习贵在坚持，不必畏惧复杂逻辑，逐题吃透模板、勤加练习就能稳步提升。永远相信日积月累的力量，持续深耕，所有努力终会兑现，美好结果正在路上等候。