滑动窗口算法详解
滑动窗口（Sliding Window）是一种常用的双指针技巧，主要用于处理连续子数组或子串的问题。它的核心思想是维护一个动态的区间 [left, right]，通过移动左右指针来调整窗口大小，从而在满足特定条件时更新结果。相比暴力枚举，滑动窗口利用问题的单调性将时间复杂度优化至 O(N)。
209. 长度最小的子数组
题目描述 给定一个含有 n 个正整数的数组和一个正整数 target，找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
思路分析 最直观的想法是暴力枚举所有子数组，计算它们的和，但这会导致 O(N^3) 的时间复杂度。我们可以先优化到 O(N^2)，利用前缀和或累加变量减少重复计算。
进一步观察发现，当 sum >= target 时，继续向右扩大窗口只会增加长度，这对求最小值没有意义。此时应该尝试收缩左边界 left，直到 sum < target。这种'扩张 - 收缩'的过程正是滑动窗口的典型特征。
代码实现
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int len = INT_MAX;
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;
}
};
虽然代码中有两层循环，但 left 和 right 各自最多移动 N 次，因此总时间复杂度为 O(N)。
3. 无重复字符的最长子串
题目描述 给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。
思路分析
我们需要维护一个不包含重复字符的窗口。当右指针 right 遇到重复字符时，必须移动左指针 left，直到窗口内不再包含该重复字符。这里可以使用哈希表（或定长数组）记录字符出现的次数。
关键点在于：当发现重复时， 不需要回到起点，而是直接跳过之前的重复位置，因为中间的部分已经不可能成为更长解的一部分。
