滑动窗口算法实战
滑动窗口是处理连续子序列问题的经典技巧，特别适合解决涉及区间和、最值或特定条件的题目。通过维护一个动态变化的窗口范围，我们往往能将时间复杂度从 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. 无重复字符的最长子串
题目信息
- 难度：中等
- 标签：哈希表、字符串、滑动窗口
解法总结
| 方法 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 集合 | O(n) | O(min(n, 128)) |
| 哈希表 | O(n) | O(min(n, 128)) |
| 数组（推荐） | O(n) | O(1) |
核心思路
这道题同样适用滑动窗口，但状态记录方式略有不同。我们需要维护一个不包含重复字符的窗口。
- 使用双指针
left和right界定窗口。 - 利用数组或哈希表记录字符出现的次数（或最后出现的位置）。
- 当遇到重复字符时，左指针直接跳到重复字符上一次出现位置的下一个位置，或者逐步收缩直到重复消除。
这里采用计数数组的方法，当某个字符计数超过 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;
}
};
复杂度分析
- 时间复杂度：O(n)，左右指针各遍历一次字符串。
- 空间复杂度：O(1)，固定大小的哈希数组（ASCII 码范围）。
小结
滑动窗口的关键在于理解何时扩张、何时收缩。对于这类题目，先明确约束条件（如和的大小、字符唯一性），再根据条件变化调整指针位置，就能高效解决问题。在实际面试或工程中，掌握这种模式能显著提升解题效率。