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