滑动窗口算法实战
滑动窗口是处理连续子序列问题的经典技巧，特别适合解决涉及区间和、最值或特定条件的题目。通过维护一个动态变化的窗口范围，我们往往能将时间复杂度从 O(n²) 优化到 O(n)。下面结合两个典型例题来深入剖析。
1. 长度最小的子数组
问题描述
给定一个包含正整数的数组和一个目标值 target，找出和大于等于 target 的连续子数组的最小长度。如果不存在这样的子数组，返回 0。
思路解析
暴力枚举所有子数组需要 O(n²) 甚至 O(n³) 的时间，对于 n = 10⁵ 的数据规模显然会超时。注意到数组元素都是正整数，这意味着当右指针向右移动时，窗口内的和单调递增；反之，左指针向右移动时，和单调递减。这一性质允许我们使用滑动窗口进行优化。
核心策略是：
- 扩展：右指针不断向右移动，将元素加入窗口。
- 收缩：一旦窗口和满足条件（sum >= target），尝试移动左指针缩小窗口，同时更新最小长度。
这种双指针配合的方式保证了每个元素最多被访问两次，时间复杂度降为 O(n)。
代码实现 (C++)
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;
}
};
边界验证
实际编码时需留意几种特殊情况：
- 数组中单个元素即满足条件。
- 所有元素之和仍小于 target，此时应返回 0。
- 初始化和变量类型是否溢出（本题为正整数，通常 int 足够）。
2. 无重复字符的最长子串
题目信息
- 难度：中等
- ：哈希表、字符串、滑动窗口
