🪟 滑动窗口/双指针经典问题课堂笔记

滑动窗口是双指针算法的特殊形式，专门解决数组/字符串的连续子区间问题，时间复杂度O(n)，比暴力O(n²)高效得多。核心思想是用两个指针l和r表示窗口的左右边界，通过移动指针来维护窗口内的状态，避免重复计算。

---

📏 固定窗口大小的滑动窗口

问题：固定长度窗口的最大不同元素数

问题描述

给定一个长度为n的数组，找出所有长度为m的连续子数组中，不同元素数量最多的那个子数组的起始位置。如果有多个，返回最左边的那个。

核心思路

• 维护一个大小固定为m的窗口
• 用计数数组b[]统计窗口内每个元素的出现次数
• 用变量s记录窗口内不同元素的数量
• 窗口向右滑动时，移除左边元素，加入右边元素，更新s和最大值

带关键注释代码

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n, a[1000010], m, ans, s, L, b[10010]; 
// a[]: 原数组
// b[]: 计数数组，统计窗口内每个元素的出现次数
// s: 当前窗口内不同元素的数量
// ans: 记录最大的不同元素数量
// L: 记录最优窗口的起始位置

signed main(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
    }
    
    int l=1, r=0; // 窗口左右边界，初始为空窗口
    while(l <= n && r <= n){
        if(r - l + 1 == m){ // 窗口大小正好是m
            // 更新最大值和起始位置
            if(s > ans){
                ans = s;
                L = l;
            }
            // 窗口向右滑动：加入右边下一个元素
            r++;
            b[a[r]]++;
            if(b[a[r]] == 1) s++; // 新元素第一次出现，不同数+1
        }
        else if(r - l + 1 > m){ // 窗口太大，需要收缩左边界
            b[a[l]]--;
            if(b[a[l]] == 0) s--; // 元素完全移出窗口，不同数-1
            l++;
        }
        else{ // 窗口太小，需要扩大右边界
            r++;
            b[a[r]]++;
            if(b[a[r]] == 1) s++;
        }
    }
    
    cout << L;
    return 0;
}

---

📐 可变窗口大小的滑动窗口

窗口大小不固定，根据窗口内的条件动态调整左右边界，找到满足条件的最长/最短窗口。

问题1：最多替换k个0的最长连续1

问题描述

给定一个二进制数组，你可以将最多k个0替换成1，求替换后能得到的最长连续1的长度。

核心思路

• 维护一个窗口，窗口内0的数量不超过k
• 用前缀和数组s[]快速计算窗口内0的数量
• 当窗口内0的数量≤k时，扩大右边界；否则收缩左边界
• 记录过程中窗口的最大长度

带关键注释代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, k, s[100010], a[100010];
// s[i]: 前i个元素中0的个数

signed main(){
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        // 计算0的前缀和
        if(a[i] == 0){
            s[i] = s[i-1] + 1;
        }else{
            s[i] = s[i-1];
        }
    }
    
    int l=1, r=1, ans=0;
    while(l <= n && r <= n){
        int zero_count = s[r] - s[l-1]; // 窗口[l,r]内0的数量
        if(zero_count <= k){ // 满足条件，可以继续扩大窗口
            ans = max(ans, r - l + 1);
            r++;
        }else{ // 不满足条件，收缩左边界
            l++;
        }
    }
    
    cout << ans;
    return 0;
}

---

问题2：包含所有类型的最小窗口长度（最小覆盖子数组）

问题描述

给定一个数组，元素有m种不同的类型，找出包含所有m种类型的最短连续子数组的长度。如果不存在，输出-1。

核心思路

• 维护一个窗口，目标是包含所有m种类型
• 用计数数组b[]统计窗口内每种类型的数量
• 用变量type记录窗口内包含的不同类型数量
• 当type < m时扩大右边界；当type == m时收缩左边界，同时记录最小窗口长度

带关键注释代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, a[1000010], b[2010];
// b[]: 计数数组，统计窗口内每种类型的出现次数
// type: 当前窗口内包含的不同类型数量

signed main(){
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    
    int l=1, r=0, ans=1e9, type=0;
    while(l <= n && r <= n){
        if(type < m){ // 还没包含所有类型，扩大右边界
            r++;
            if(b[a[r]] == 0) type++; // 新类型加入窗口
            b[a[r]]++;
        }else{ // 已经包含所有类型，尝试收缩左边界找更小窗口
            ans = min(ans, r - l + 1); // 更新最小窗口长度
            b[a[l]]--;
            if(b[a[l]] == 0) type--; // 某类型完全移出窗口
            l++;
        }
    }
    
    if(ans == 1e9) cout << -1; // 没有找到满足条件的窗口
    else cout << ans;
    return 0;
}

---

问题3：包含所有类型的最小花费窗口

问题描述

给定一个数组，元素有m种不同的类型，每种类型有对应的花费c[i]。找出包含所有m种类型的连续子数组中，总花费最小的那个。如果最小花费超过v或不存在，输出"NO ans"；否则输出v - 最小花费。

核心思路

• 在最小覆盖子数组的基础上，增加总花费的统计
• 用变量s记录当前窗口的总花费
• 当包含所有类型时，更新最小花费，然后收缩左边界

带关键注释代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

int n, m, v, a[1000010], b[2010], c[2010], s;            
// c[]: 每种类型的花费
// s: 当前窗口的总花费

signed main(){
    cin >> n >> m >> v;          
    for(int i=1; i<=m; i++){
        cin >> c[i]; // 输入每种类型的花费
    }
    for(int i=1; i<=n; i++) cin >> a[i];
    
    int l=1, r=0, ans=1e9, type=0;
    s=0;
    while(l <= n && r <= n){
        if(type < m){ // 扩大右边界
            r++;
            if(b[a[r]] == 0) type++;
            b[a[r]]++;
            s = s + c[a[r]]; // 加上新元素的花费
        }else{ // 收缩左边界
            ans = min(ans, s); // 更新最小花费
            b[a[l]]--;
            if(b[a[l]] == 0) type--;
            s = s - c[a[l]]; // 减去移出元素的花费
            l++;
        }
    }
    
    // 判断结果
    if(ans == 1e9 || ans > v){
        cout << "NO ans";
    }else{
        cout << v - ans;
    }
    return 0;
}

---

问题4：和≤m的最长子数组

问题描述

给定一个所有元素都是正数的数组，找出和不超过m的最长连续子数组的长度。

核心思路

• 利用前缀和快速计算窗口内的和
• 因为所有元素都是正数，所以窗口和随右边界扩大而单调递增，随左边界收缩而单调递减
• 当和≤m时扩大右边界，否则收缩左边界，记录最大窗口长度

带关键注释代码

#include <bits/stdc++.h>
using namespace std;

int n, m, a[100010], s[100010], ans;
// s[i]: 前i个元素的前缀和

int main(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    
    int l=1, r=1;
    while(l <= n && r <= n){
        int sum = s[r] - s[l-1]; // 窗口[l,r]的和
        if(sum <= m){ // 满足条件，扩大窗口
            ans = max(ans, r - l + 1);
            r++;
        }else{ // 不满足条件，收缩窗口
            l++;
        }
    }
    
    cout << ans;
    return 0;
}

---

问题5：和≥m的最短子数组

问题描述

给定一个所有元素都是正数的数组，找出和至少为m的最短连续子数组的长度。如果不存在，输出0。

核心思路

• 与上一个问题相反，目标是找满足和≥m的最短窗口
• 当和<m时扩大右边界；当和≥m时，记录当前窗口长度，然后收缩左边界尝试找更短的窗口

带关键注释代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define int long long

long long a[N], ans=INT_MAX, s[N];

signed main(){
    int n, m;
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> a[i];
        s[i] = s[i-1] + a[i];
    }
    
    int l=1, r=1;
    while(l <= n && r <= n){
        int sum = s[r] - s[l-1];
        if(sum >= m){ // 满足条件，尝试收缩左边界找更短窗口
            ans = min(ans, r - l + 1);
            l++;
        }else{ // 不满足条件，扩大右边界
            r++;
        }
    }
    
    if(ans == INT_MAX) cout << 0; // 没有找到满足条件的窗口
    else cout << ans;
    return 0; 
}

---

💡 核心总结

1. 滑动窗口适用条件

• 问题是关于连续子数组/子字符串的
• 窗口内的状态可以通过**O(1)**时间更新
• 窗口的单调性：当右边界向右移动时，左边界只能向右移动（不能回头）

2. 固定窗口vs可变窗口

类型	特点	适用场景
固定窗口	窗口大小固定不变	求所有长度为k的子数组的最大值/最小值/不同元素数等
可变窗口	窗口大小动态调整	求满足某个条件的最长/最短子数组

3. 可变窗口通用模板

int l=1, r=0, ans=初始值;
while(l <= n && r <= n){
    if(不满足条件){
        扩大右边界(r++)
        更新窗口状态
    }else{
        更新答案ans
        收缩左边界(l++)
        更新窗口状态
    }
}

4. 易错点提醒

1. 边界条件：注意l和r的初始值和循环条件，避免数组越界
2. 状态更新：窗口移动时，一定要正确更新窗口内的状态（计数、和、类型数等）
3. 元素为正：和相关的滑动窗口问题只适用于所有元素都是正数的情况，如果有负数需要用前缀和+单调栈
4. 初始化：求最大值时ans初始化为0，求最小值时ans初始化为无穷大
5. 无解情况：最后一定要判断ans是否还是初始值，处理无解的情况