博客详情 - oirush

admin 的博客
滑动窗口 (Sliding Window)
admin SU @ 2026-6-7 19:56:26

算法概述

滑动窗口（Sliding Window）是一种在数组或字符串上维护一个连续子区间（窗口），并让该窗口在数据结构上滑动的算法技巧。通过动态调整窗口的左右边界，可以在单次遍历中解决大量子数组/子串问题，将原本 O(n²) 的暴力枚举优化为 O(n)。

滑动窗口本质上可以看作是双指针的一种特殊形式，其指针移动具有明确的规则：右指针扩展窗口，左指针收缩窗口。

核心思想

窗口扩展：右指针 right 不断向右移动，将新元素纳入窗口，更新窗口内的状态。
窗口收缩：当窗口内的状态不满足条件时（或为了寻找更优解），左指针 left 向右移动，将元素移出窗口，同时更新窗口状态。
答案更新：在窗口收缩的合适时机（通常是窗口重新满足条件或刚刚不满足时），记录/更新答案。

滑动窗口分为两种主要类型：

类型	描述
不定长窗口	窗口长度不固定，根据条件动态调整。
定长窗口	窗口长度固定为 k，从头滑到尾。

算法步骤 / 伪代码

不定长滑动窗口通用模板

function slidingWindow(s):
    left = 0
    result = 0
    window_state = {}                   // 维护窗口内状态（如字符频率、和等）

    for right = 0 to s.length - 1:      // 右指针扩展
        add s[right] to window_state    // 将当前元素加入窗口

        while window_state violates condition:  // 窗口不满足条件时收缩
            remove s[left] from window_state
            left++

        // 此时窗口满足条件，更新答案
        result = max(result, right - left + 1)  // 或其他更新方式

    return result

定长滑动窗口模板

function fixedSlidingWindow(arr, k):
    window_sum = sum(arr[0..k-1])       // 初始窗口
    result = window_sum

    for i = k to arr.length - 1:
        window_sum += arr[i]            // 加入新元素
        window_sum -= arr[i - k]        // 移除最左元素
        result = max(result, window_sum)

    return result

C++ 代码实现

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
using namespace std;

// ============ 不定长窗口 ============

// LeetCode 3：无重复字符的最长子串
int lengthOfLongestSubstring(string s) {
    unordered_set<char> window;  // 窗口内字符集合
    int left = 0;
    int maxLen = 0;

    for (int right = 0; right < s.size(); ++right) {
        // 窗口中已存在 s[right]，收缩左边界直到不再重复
        while (window.count(s[right])) {
            window.erase(s[left]);
            ++left;
        }
        window.insert(s[right]);
        maxLen = max(maxLen, right - left + 1);
    }
    return maxLen;
}

// LeetCode 209：长度最小的子数组
int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0;
    int sum = 0;
    int minLen = INT_MAX;

    for (int right = 0; right < nums.size(); ++right) {
        sum += nums[right];

        // 当窗口和 >= target 时，尝试收缩左边界找更短的满足条件的子数组
        while (sum >= target) {
            minLen = min(minLen, right - left + 1);
            sum -= nums[left];
            ++left;
        }
    }
    return (minLen == INT_MAX) ? 0 : minLen;
}

// LeetCode 76：最小覆盖子串
string minWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0;
    int valid = 0;               // 已满足条件的字符种类数
    int start = 0, minLen = INT_MAX;

    for (int right = 0; right < s.size(); ++right) {
        char c = s[right];
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) {
                ++valid;         // 一个字符的数量达标
            }
        }

        // 所有字符都满足条件时，尝试收缩左边界
        while (valid == need.size()) {
            // 更新最小覆盖子串
            if (right - left + 1 < minLen) {
                start = left;
                minLen = right - left + 1;
            }

            char d = s[left];
            ++left;
            if (need.count(d)) {
                if (window[d] == need[d]) {
                    --valid;     // 移除后该字符不再达标
                }
                window[d]--;
            }
        }
    }
    return (minLen == INT_MAX) ? "" : s.substr(start, minLen);
}

// LeetCode 438：找到字符串中所有字母异位词
vector<int> findAnagrams(string s, string p) {
    unordered_map<char, int> need, window;
    for (char c : p) need[c]++;

    int left = 0, valid = 0;
    vector<int> result;

    for (int right = 0; right < s.size(); ++right) {
        char c = s[right];
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) ++valid;
        }

        // 定长窗口：长度等于 p 时判断并收缩
        while (right - left + 1 >= p.size()) {
            if (valid == need.size()) {
                result.push_back(left);
            }
            char d = s[left];
            ++left;
            if (need.count(d)) {
                if (window[d] == need[d]) --valid;
                window[d]--;
            }
        }
    }
    return result;
}

// ============ 定长窗口 ============

// 定长窗口最大子数组和
int maxSumFixedWindow(vector<int>& arr, int k) {
    int sum = 0;
    // 计算初始窗口的和
    for (int i = 0; i < k; ++i) {
        sum += arr[i];
    }
    int maxSum = sum;

    // 窗口滑动
    for (int i = k; i < arr.size(); ++i) {
        sum += arr[i] - arr[i - k];   // 加新减旧
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

// 定长窗口：大小为 k 的子数组平均值
vector<double> findAverages(vector<int>& arr, int k) {
    vector<double> result;
    int sum = 0;
    for (int i = 0; i < k; ++i) sum += arr[i];
    result.push_back((double)sum / k);

    for (int i = k; i < arr.size(); ++i) {
        sum += arr[i] - arr[i - k];
        result.push_back((double)sum / k);
    }
    return result;
}

// ============ 主函数 ============
int main() {
    cout << "========== 滑动窗口算法演示 ==========" << endl << endl;

    // ---- LeetCode 3：无重复字符的最长子串 ----
    string s1 = "abcabcbb";
    cout << "【LeetCode 3：无重复字符的最长子串】" << endl;
    cout << "字符串: \"" << s1 << "\"" << endl;
    cout << "最长无重复子串长度: " << lengthOfLongestSubstring(s1)
         << " (期望: 3, 子串 \"abc\")" << endl;

    string s2 = "pwwkew";
    cout << "字符串: \"" << s2 << "\"" << endl;
    cout << "最长无重复子串长度: " << lengthOfLongestSubstring(s2)
         << " (期望: 3, 子串 \"wke\")" << endl;

    // ---- LeetCode 209：长度最小的子数组 ----
    vector<int> nums209 = {2, 3, 1, 2, 4, 3};
    int target = 7;
    cout << "\n【LeetCode 209：长度最小的子数组】" << endl;
    cout << "数组: ";
    for (int x : nums209) cout << x << " ";
    cout << "\n目标和: " << target << endl;
    cout << "最短子数组长度: " << minSubArrayLen(target, nums209)
         << " (期望: 2, 子数组 [4,3])" << endl;

    // ---- LeetCode 76：最小覆盖子串 ----
    string s76 = "ADOBECODEBANC";
    string t76 = "ABC";
    cout << "\n【LeetCode 76：最小覆盖子串】" << endl;
    cout << "s: \"" << s76 << "\", t: \"" << t76 << "\"" << endl;
    cout << "最小覆盖子串: \"" << minWindow(s76, t76)
         << "\" (期望: \"BANC\")" << endl;

    // ---- LeetCode 438：找到字符串中所有字母异位词 ----
    string s438 = "cbaebabacd";
    string p438 = "abc";
    cout << "\n【LeetCode 438：找到字符串中所有字母异位词】" << endl;
    cout << "s: \"" << s438 << "\", p: \"" << p438 << "\"" << endl;
    auto anagrams = findAnagrams(s438, p438);
    cout << "异位词起始下标: ";
    for (int idx : anagrams) cout << idx << " ";
    cout << "(期望: 0 6)" << endl;

    // ---- 定长窗口：大小为 k 的子数组最大和 ----
    vector<int> arr = {1, 4, 2, 10, 23, 3, 1, 0, 20};
    int k = 4;
    cout << "\n【定长窗口：大小为 " << k << " 的子数组最大和】" << endl;
    cout << "数组: ";
    for (int x : arr) cout << x << " ";
    cout << "\n最大和: " << maxSumFixedWindow(arr, k) << " (期望: 39, 子数组 [4,2,10,23])" << endl;

    // ---- 定长窗口：大小为 k 的子数组平均值 ----
    cout << "\n【定长窗口：大小为 " << k << " 的子数组平均值】" << endl;
    auto avgs = findAverages(arr, k);
    cout << "各窗口平均值: ";
    for (double avg : avgs) {
        cout << avg << " ";
    }
    cout << endl;

    return 0;
}

复杂度分析

类型	时间复杂度	空间复杂度	说明
不定长窗口	O(n)	O(k) 或 O(字符集)	左右指针各遍历一次，均摊 O(n)
定长窗口	O(n)	O(1)	每个元素进窗口一次、出窗口一次

时间复杂度：虽然代码中存在嵌套的 while 循环，但左指针 left 和右指针 right 各自只会从 0 移动到 n（每个元素最多进窗口一次、出窗口一次），均摊时间复杂度为 O(n)。
空间复杂度：取决于窗口状态的存储方式。对于字符类问题，通常需要一个哈希表或数组来维护窗口内的字符频率，空间复杂度为 O(字符集大小)；对于数值类问题，通常只需维护一个变量（如窗口和），空间复杂度为 O(1)。

应用场景

子串问题：
- 无重复字符的最长子串（LeetCode 3）
- 最小覆盖子串（LeetCode 76）
- 找到字符串中所有字母异位词（LeetCode 438）
- 串联所有单词的子串（LeetCode 30）
子数组问题：
- 长度最小的子数组（LeetCode 209）
- 乘积小于 K 的子数组（LeetCode 713）
- 和为 K 的子数组（LeetCode 560，需结合前缀和）
定长窗口问题：
- 大小为 K 的子数组最大和
- 大小为 K 的滑动窗口内的最大值（LeetCode 239，需结合单调队列）
- 大小为 K 的子数组的平均值
替换/修改类问题：
- 替换后的最长重复字符（LeetCode 424）
- 最大连续 1 的个数 III（LeetCode 1004）
流式数据处理：如实时统计最近一段时间的请求频率、移动平均值等。

经典例题

LeetCode 3 — 无重复字符的最长子串

题目描述：给定一个字符串 s，找出其中不含有重复字符的最长子串的长度。

示例：

输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

滑动窗口解法思路：

维护一个窗口 [left, right]，窗口内字符都不重复。
right 不断右移，将新字符加入窗口。
若新字符已在窗口中，则不断右移 left，直到将重复字符移出窗口。
每次窗口合法时，更新最大长度 = max(maxLen, right - left + 1)。
使用哈希集合 unordered_set 或频率数组维护窗口内的字符。

LeetCode 209 — 长度最小的子数组

题目描述：给定一个含有 n 个正整数的数组和一个正整数 target。找出该数组中满足其和 ≥ target 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例：

输入: target = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的子数组。

滑动窗口解法思路：

right 不断右移，累加窗口和 sum。
当 sum >= target 时，尝试收缩 left 以寻找更短的满足条件的子数组。
每次收缩前更新最小长度 minLen。
由于数组中都是正整数，窗口和具有单调性，适合滑动窗口。

（完整 C++ 代码已包含在上方的代码实现中）

滑动窗口 (Sliding Window)

算法概述

核心思想

算法步骤 / 伪代码

不定长滑动窗口通用模板

定长滑动窗口模板

C++ 代码实现

复杂度分析

应用场景

经典例题

LeetCode 3 — 无重复字符的最长子串

LeetCode 209 — 长度最小的子数组

状态

开发

支持

关于

滑动窗口 (Sliding Window)

算法概述

核心思想

算法步骤 / 伪代码

不定长滑动窗口通用模板

定长滑动窗口模板

C++ 代码实现

复杂度分析

应用场景

经典例题

LeetCode 3 — 无重复字符的最长子串

LeetCode 209 — 长度最小的子数组

状态

开发

支持

关于

还没有账户？

登录