跳转至

滑动窗口

前置知识

双指针

目标

滑动窗口模板题

滑动窗口

滑动窗口是双指针技巧的一种常见形式。用 l、r 表示当前连续区间，一般在右端加入新元素，并按条件从左端删除元素，同时维护窗口内的和、计数、最值等信息。

l 在一轮中可以移动多次，窗口长度也可以增大或减小；它们都不是区分“滑动窗口”和“双指针”的依据。对于定长窗口，每加入一个右端元素通常删除一个左端元素；对于变长窗口，则常用 while 移动左端直到重新满足条件。

a数组中所有长度为m的子串，和b数组中的元素对比，至少有k个是相同的

看窗口内相同的元素的个数，是否>=k

#include <bits/stdc++.h>

using namespace std;

int T, n, m, k;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> T;
    while (T--) {
        cin >> n >> m >> k;
        vector<int> a(n), b(m);

        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < m; i++) cin >> b[i];

        map<int, int> cnta, cntb;
        for (int i = 0; i < m; i++) cntb[b[i]]++;

        int cnt = 0, ret = 0;
        for (int i = 0, j = 0; i < n; i++) {
            while (i - j + 1 > m) {
                cnta[a[j]]--;
                if (cnta[a[j]] < cntb[a[j]]) cnt--;
                j++;
            }

            if (cnta[a[i]] < cntb[a[i]]) cnt++;
            cnta[a[i]]++;

            if (i >= m - 1 && cnt >= k) {
                ret++;
            }
        }

        cout << ret << '\n';
    }

    return 0;
}

POJ2823 Sliding Window

// 结合了单调队列
#include <iostream>
#include <cstdio>

using namespace std;

const int N = 1e6 + 10;

int a[N], q[N], n, k;
int hh, tt;

int main(){
    cin >> n >> k;
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    hh = 0, tt = -1;
    for (int i = 0; i < n; i++){
        // 窗口滑出去了
        if (hh <= tt && i - k + 1 > q[hh]) hh++; 

        // 较小的值入队
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;

        q[++tt] = i;

        // 窗口是满的就输出,没满k宽度的时候，是不可输出的
        // 队列是单调递增的，队头是窗口里的最小值
        if (i - k + 1 >= 0) printf("%d ", a[q[hh]]);
    }
    puts("");

    hh = 0, tt = -1;
    for (int i = 0; i < n; i++){
        // 窗口滑出去了
        if (hh <= tt && i - k + 1 > q[hh]) hh++; 

        // 较小的值入队
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;

        q[++tt] = i;

        // 窗口是满的就输出,没满k宽度的时候，是不可输出的
        if (i - k + 1 >= 0) printf("%d ", a[q[hh]]);
    }
    puts("");


    return 0;
}

参考

  • https://blog.csdn.net/lyqptp233/article/details/113774583 算法系列--滑动窗口与双指针
  • https://www.acwing.com/solution/content/240594/