滑动窗口算法实战
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 |
第六步：编写代码
class Solution {
public:
int minSubArrayLen(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++ 最优解）
class Solution {
public:
int lengthOfLongestSubstring(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;
}
};