给定一个长度为N的数列，求有多少个区间满足区间中出现最多的数的个数大于等于K?c++代码

以下是基于滑动窗口的解法，时间复杂度为O(N)。

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

const int MAXN = 1e5 + 5;

int n, k, ans;
int cnt[MAXN], freq[MAXN]; // cnt数组记录当前窗口中每个数出现的次数，freq数组记录每个数在所有窗口中出现的最大次数

int main() {
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int l = 0;
    for (int r = 0; r < n; ++r) {
        ++cnt[a[r]];
        freq[cnt[a[r]]] = max(freq[cnt[a[r]]], cnt[a[r]]);
        while (r - l + 1 > freq[k]) { // 如果当前窗口中出现最多的数的个数小于k，则不断收缩左端点
            --cnt[a[l]];
            if (cnt[a[l]] < freq[k]) { // 如果左端点指向的数已经不再是出现最多的数，则更新freq数组
                freq[cnt[a[l]]] = max(freq[cnt[a[l]]], cnt[a[l]]);
            }
            ++l;
        }
        ans += r - l + 1;
    }
    cout << ans << endl;

    return 0;
}