简单滑动窗口算法

题目简述

长度为n的数组a，求有多少个存在某元素出现次数 >= m 的连续子区间[l,r]

算法分析

我们可以发现：

若子区间[i,j]不满足情况，固定i不动，j每次后移一步，一次添加一个元素，直到恰好满足 num[a[j]] == m 时，所有以i为起点，以j后面为终点的区间都满足条件，则ans += n-j。

这样我们就记录了所有以 i 为起点的情况，那么while(a[i]!=a[j])，删去头元素i后区间仍然满足条件，即 [i+1,j]也是首次满足条件，同样ans += n-j。

总结起来，我们就是要遍历区间起点 i ，每次找到使区间 [i,j] 第一次满足条件的 j，然后 ans 累加上以 i 为起点的所有情况。即双 for 双指针，时间复杂度 O(n^2)。

所以这里可以用滑动窗口来保存区间信息，使用 while(a[i]!=a[j]) 一次右移多次起点指针，记录多个 i 的情况，这样就只用 单层 for 即可，每个元素进入窗口一次，出窗口一次，时间复杂度 O(n)

C++代码

此题n和m只有40万，ans却卡long long，浪费一次提交。

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


long long No9_SlidingWindow(int n, int m, const vector<int>& a) {
    long long ans = 0;
    int i = 0;
    unordered_map<int, int> num;
    for (int j = 0; j < n; j++) {   // [i,j]窗口长度为 j-i+1
        if (++num[a[j]] != m)continue;  // 元素j进入滑动窗口
        ans += n - j;   //以i为起点的全部满足区间
        while (a[i] != a[j]) {  //删去头元素仍然满足条件
            num[a[i]]--;
            i++;
            ans += n - j;
        }
        //此时删去头元素就不满足条件了，但以头元素为起点的区间已经加到ans中了
        // 仍然删去头元素，使此时的区间不满足条件，同时使以i为起点的区间没被累加过
        num[a[i]]--;
        i++;
    }
    return ans;
}

int main(){
    int n,m;
    cin>>n>>m;
    vector<int>a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    
    cout<<No9_SlidingWindow(n, m, a)<<'\n';
    return 0;
}