优选算法——滑动窗口
优选算法——滑动窗口
1.长度最小的子数组
解题原理
📋 解题步骤
第一步：理解题意
- 找一个连续子数组，使其和 ≥ target，且长度最小
- 数组元素都是正整数（关键性质）
- 无解返回 0
第二步：分析暴力解法
- 枚举所有子数组：O(n²) 或 O(n³)
- 对于 n = 10⁵ 会超时
第三步：寻找优化点
- 正整数 → 窗口扩展时和单调递增
- 可以用滑动窗口优化
第四步：设计滑动窗口
遍历右指针： 扩展窗口 从右边进窗口 判断： 如果 sum >= target： 更新最小长度 收缩窗口 从左边出窗口 第五步：手动模拟
| 步骤 | left | right | 窗口 | sum | result |
|---|---|---|---|---|---|
| 4 | 0 | 3 | [2,3,1,2] | 8 | 4 |
| 7 | 2 | 4 | [1,2,4] | 7 | 3 |
| 10 | 4 | 5 | [4,3] | 7 | 2 |
第六步：编写代码
classSolution{public:intminSubArrayLen(int target, vector<int>& nums){int len=INT_MAX;int n=nums.size();int sum=0;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;}};第七步：验证边界
- 单元素、无解、总和不足等情况
第八步：复杂度
- 时间：O(n)
- 空间：O(1)
2. 无重复字符的最长子串
题目信息
- 题目：LCR 016. 无重复字符的最长子串（与主站第3题相同）
- 难度：中等
- 标签：哈希表、字符串、滑动窗口
解法总结
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 集合 | O(n) | O(min(n, 128)) |
| 哈希表 | O(n) | O(min(n, 128)) |
| 数组（推荐） | O(n) | O(1) |
核心思路
滑动窗口法：
- 用双指针维护一个无重复字符的窗口
- 用哈希表/数组记录每个字符最后出现的位置
遇到重复字符时，左指针直接跳到重复字符的下一个位置
代码示例（C++ 最优解）
classSolution{public:intlengthOfLongestSubstring(string s){int hash[128]={0};int ret=0;int n=s.size();for(int left=0,right=0;right<n;right++){ hash[s[right]]++;//进窗口while(hash[s[right]]>1)//判断{ hash[s[left++]]--;//出窗口} ret=max(ret,right-left+1);}return ret;}}; hash[s[left++]]--;//出窗口} ret=max(ret,right-left+1);}return ret;}};
