滑动窗口：原理、图解与 C++ 实战

一、什么是滑动窗口

滑动窗口（Sliding Window）是双指针的一种特殊形态：两个指针 left、right 同向运动，夹在它们之间的连续子数组/子串就像一个"窗口"，通过 right 右扩和 left 右缩来调整窗口的位置与大小，从而找到满足条件的解。

它的典型应用是"在数组/字符串中找满足某种条件的连续子区段"——求最长、最短、恰好 k 个、和等于某值等。如果用暴力枚举所有子区段是 O(n²) 甚至 O(n³)，用滑动窗口可以降到 O(n)。

1.1 两种窗口

二、核心原理与图解

理解滑动窗口的关键，是理解"窗口为什么是合法的"。right 主动扩张让窗口变大，当窗口不满足条件时 left 被动收缩来恢复合法性——这种"扩张-收缩"的交替运动保证每次操作后窗口都有意义。

2.1 定长窗口过程图

以数组 [1, 3, -1, 5, 2, 7] 求所有长度为 3 的子数组的最大值为例。窗口大小固定为 3，每步整体右移一格。

2.2 变长窗口扩张收缩过程图

变长窗口更复杂：right 主动右扩，当窗口不合法时 left 右缩。以"和 ≥ 7 的最短子数组"为例，数组 [2, 3, 1, 2, 4, 3]。

2.3 与双指针关系图

滑动窗口和双指针并非互斥，滑动窗口是同向双指针的子集。下图直观展示它们的关系。

2.4 复杂度分析

三、通用模板

滑动窗口的核心是"窗口内维护什么、收缩条件是什么"。下面给出定长和变长两种骨架。

3.1 变长窗口模板（找最短）

// 变长窗口通用模板：找满足条件的最短子数组
int minSubArrayLen(int target, const vector<int>& nums) {
    int n = (int)nums.size();
    int left = 0, sum = 0, ans = INT_MAX;
    for (int right = 0; right < n; ++right) {
        sum += nums[right];          // 右扩：进入窗口
        while (sum >= target) {      // 满足条件 → 尝试收缩
            ans = min(ans, right - left + 1);
            sum -= nums[left++];     // 左缩：移出窗口
        }
    }
    return ans == INT_MAX ? 0 : ans;
}

3.2 定长窗口模板

// 定长窗口通用模板：长度为 k 的子数组最大值
vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    vector<int> res;
    deque<int> dq;  // 存下标，对应值单调递减
    for (int i = 0; i < (int)nums.size(); ++i) {
        // 1. 队首出窗
        if (!dq.empty() && dq.front() == i - k) dq.pop_front();
        // 2. 队尾维护单调性
        while (!dq.empty() && nums[dq.back()] <= nums[i]) dq.pop_back();
        dq.push_back(i);
        // 3. 窗口已满 → 队首即最大
        if (i >= k - 1) res.push_back(nums[dq.front()]);
    }
    return res;
}

四、示例一：长度最小的子数组

题目（LeetCode 209）：给定一个正整数数组 nums 和目标 target，找出和 ≥ target 的长度最小的连续子数组。不存在返回 0。

4.1 示例

输入：nums = [2,3,1,2,4,3]，target = 7
输出：2（子数组 [4,3]）

4.2 C++ 代码

#include <vector>
#include <climits>
using namespace std;

int minSubArrayLen(int target, const vector<int>& nums) {
    int n = (int)nums.size();
    int left = 0, sum = 0, ans = INT_MAX;
    for (int right = 0; right < n; ++right) {
        sum += nums[right];            // 右扩：nums[right] 进窗口
        while (sum >= target) {        // 满足条件 → 持续收缩求更短
            ans = min(ans, right - left + 1);
            sum -= nums[left++];       // 左缩：nums[left] 出窗口
        }
    }
    return ans == INT_MAX ? 0 : ans;
}

注意"正整数"这个条件保证了 sum 单调——right 扩 sum 必增、left 缩 sum 必减，所以收缩不会"先满足再满足"无限循环。如果数组含负数，此模板失效，需用前缀和 + 单调队列。

五、示例二：无重复字符的最长子串

题目（LeetCode 3）：给定字符串 s，找出不含重复字符的最长子串的长度。

5.1 思路：哈希维护窗口字符计数

窗口合法条件是"窗口内无重复字符"。用哈希表记录窗口内每个字符出现次数。right 右扩加入字符后，如果该字符出现次数 > 1，说明有重复——left 持续右缩直到该字符次数恢复为 1。

5.2 C++ 代码

#include <string>
#include <unordered_map>
using namespace std;

int lengthOfLongestSubstring(const string& s) {
    unordered_map<char, int> cnt;  // 窗口内字符计数
    int left = 0, ans = 0;
    for (int right = 0; right < (int)s.size(); ++right) {
        char c = s[right];
        cnt[c]++;                          // 右扩：字符进窗口
        while (cnt[c] > 1) {             // 出现重复 → 左缩
            cnt[s[left]]--;                // 字符出窗口
            left++;
        }
        ans = max(ans, right - left + 1);  // 每次循环结束窗口必合法
    }
    return ans;
}

六、示例三：滑动窗口最大值

题目（LeetCode 239）：给定数组 nums 和窗口大小 k，窗口从最左端滑动到最右端，返回每个窗口内的最大值。

6.1 思路：定长窗口 + 单调队列

定长窗口每次只进出各一个元素，最大值如果在窗口内仍存活就直接复用；如果出窗的是最大值，要能 O(1) 拿到次大值——这正是单调队列的拿手好戏。队列存下标，对应值单调递减，队首永远是当前窗口最大。

6.2 C++ 代码

#include <vector>
#include <deque>
using namespace std;

vector<int> maxSlidingWindow(const vector<int>& nums, int k) {
    vector<int> res;
    deque<int> dq;  // 存下标，对应值从队首到队尾单调递减

    for (int i = 0; i < (int)nums.size(); ++i) {
        // 1. 队首出窗：下标 ≤ i-k 已不在窗口内
        while (!dq.empty() && dq.front() <= i - k) {
            dq.pop_front();
        }
        // 2. 队尾维护单调性：弹掉所有 ≤ 当前值的下标
        while (!dq.empty() && nums[dq.back()] <= nums[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        // 3. 窗口已满：队首即最大值
        if (i >= k - 1) {
            res.push_back(nums[dq.front()]);
        }
    }
    return res;
}

七、总结与适用场景

典型题目清单

• LeetCode 209：长度最小的子数组（变长窗口，基础）
• LeetCode 3：无重复字符的最长子串（变长 + 哈希）
• LeetCode 239：滑动窗口最大值（定长 + 单调队列）
• LeetCode 76：最小覆盖子串（变长 + 哈希，进阶）
• LeetCode 438：找到字符串中所有字母异位词（定长 + 计数）
• LeetCode 567：字符串的排列（定长 + 计数）
• LeetCode 424：替换后的最长重复字符（变长 + 计数）
• LeetCode 480：滑动窗口中位数（定长 + 双堆）
• LeetCode 1456：定长子串中元音的最大数目（定长 + 计数）