滑动窗口

滑动窗口的核心在于维护窗口的左指针和右指针的移动条件,有时可以一次移动多位,有时只能移动一位。移动多位的条件要求跳过的情况已经被覆盖,本例左指针一次移动多位。

#include<iostream>
#include<vector>
#include<unordered_map>
using namespace std;
int main(){
    long long n, m;
    cin >> n >> m;
    vector<int> nums(n, 0);
    unordered_map<int, int> myMap;
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    for (int i = 0; i < m - 1; ++i) {
        ++myMap[nums[i]];
    }
    long long l = 0; // 滑动区间的左端点为0
    long long ans = 0; 
    for (long long i = m - 1; i < n; ++i) {
        int num = nums[i]; // 当前遍历的端点为num
        ++myMap[num];
        if (myMap[nums[i]] == m) {
            long long last_l = l;
            while (nums[l] != num) {
                --myMap[nums[l]];
                ++l;
            }  // 此时左右端点都是num 
            ans += (l + 1 - last_l) * (n - i);
            --myMap[nums[l]];
            ++l;
        }
    }
    cout << ans << endl;
    return 0;
}