滑动窗口算法实战
本文针对两个经典的滑动窗口问题展开解析：长度最小的子数组和无重复字符的最长子串。通过对比暴力解法，展示双指针不回退策略如何将时间复杂度优化至 O(N)。
1. 长度最小的子数组
题目链接： 209. 长度最小的子数组 - LeetCode
问题分析
给定一个包含 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
解法思路
暴力枚举所有子数组的时间复杂度为 O(N²)，在数据量较大时会超时。我们可以利用滑动窗口的思想来优化。
维护一个窗口 [left, right]，不断向右移动右指针 right 扩大窗口，累加窗口内元素和 sum。当 sum >= target 时，记录当前窗口长度，并尝试移动左指针 left 缩小窗口，直到 sum < target。在这个过程中，我们不需要回溯 left 指针，因为对于当前的 right，一旦找到满足条件的最小 left，下一个 right 对应的最优 left 一定在当前 left 的右侧或相同位置。
C++ 代码实现
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(), sum = 0, len = INT_MAX;
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)。虽然有两层循环结构，但
left和right指针都只向右移动，每个元素最多被访问两次。 - 空间复杂度： O(1)。
2. 无重复字符的最长子串
题目链接： 3. 无重复字符的最长子串 - LeetCode
问题分析
给定一个字符串 s，请你找出其中不含有重复字符的 最长子串 的长度。
解法思路
同样采用滑动窗口。我们需要保证窗口内的字符都是唯一的。使用哈希表（或数组）统计窗口内字符的出现频次。
- 右指针
right遍历字符串，将字符加入窗口。 - 如果某字符频次超过 1，说明出现重复，此时需要移动左指针
left直到该字符频次降回 1。 - 每次更新最大长度
ret。
C++ 代码实现
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128] = {0}; // ASCII 码范围足够
int n = s.size(), left = 0, right = 0, ret = 0;
while (right < n) {
hash[s[right]]++; // 字符入窗口
while (hash[s[right]] > 1) { // 有重复，收缩左边界
hash[s[left++]]--;
}
ret = max(ret, right - left + 1); // 更新结果
right++; // 继续扩展
}
return ret;
}
};
关键点总结
- 哈希表的作用： 快速判断当前字符是否已在窗口中存在。
- 指针不回退： 这是滑动窗口效率高的核心。一旦确定某个位置作为左边界不再可能产生更优解，就永久跳过它。
- 边界处理： 注意空字符串或全重复字符的情况，上述逻辑已涵盖。
掌握这两个模板后，类似的变体问题（如含 K 个不同字符、最小覆盖子串等）都能迎刃而解。
