🔥小龙报：个人主页
🎬作者简介：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 代码
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int l = 0,r = 0,n = nums.size();
int sum = 0,len = 1e6 + 10;
while(r < n)
{
//进窗口
sum += nums[r];
//判断
while(sum >= target)
{
len = min(len,r - l + 1);
sum -= nums[l++]; //出窗口
}
r++;
}
return len == 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 代码
class Solution {
public:
int lengthOfLongestSubstring(string s)
{
int h[128] = {0}; //用数组模拟哈希表
int l = 0,r = 0,n = s.size();
int ret = 0;
while(r < n)
{
h[s[r]]++; //进窗口
while(h[s[r]] > 1) //判断 + 出窗口（此时窗口非法）
h[s[l++]]--;
ret = max(ret,r - l + 1); //更新合法窗口的结果
r++;
}
return ret;
}
};
时间复杂度 : O（N）
总结与每日励志
✨两道例题完整覆盖滑动窗口核心逻辑，关键在于利用单调性保证指针只前进不回退，搭配数组哈希快速统计字符频次。刷题时牢记三步模板：右指针扩张窗口，满足条件就收缩左边界，实时更新最优答案。算法学习贵在坚持，不必畏惧复杂逻辑，逐题吃透模板、勤加练习就能稳步提升。永远相信日积月累的力量，持续深耕，所有努力终会兑现，美好结果正在路上等候。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/2401_87342824/article/details/162723550
