链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
题目描述
YangQiShaoNian has an array of length nnn, a subarray [l,r][l,r][l,r] in the array is good if and only if each element in al,al+1,…ar appears exactly kkk times in the current interval.
For example, for a=[1,1,2,3,2,3,1]and k=2, the intervals [1,2], [3,6], [1,6], etc., are all good. However, [1,3] does not meet the condition because the element 2 appears only once, and [1,7] does not meet the condition because the element 1 appears 3 times.
Please help YangQiShaoNian to find the number of good intervals that can be selected.
输入描述:
The first line contains an integer T(1≤T≤), indicating the number of test cases.For each test case:The first line contains two integers n(1≤n≤2⋅),k(1≤k≤n).The second line contains nnn integers a1…an(0≤ai≤) --- each element of the array.It is guaranteed that the total sum of nnn for all test cases does not exceed 2⋅.
输出描述:
For each test case:Only output one line containing an integer, representing the answer.
示例1
输入
4
3 2
1 2 2
3 1
1 2 3
6 2
1 1 4 5 1 4
6 3
1 2 1 1 1 1
输出
1
6
1
2
题目大意：有 t 组样例，给你一个长度为 n 的数组和一个不大于 n 的正整数 k ，问：有多少个子区间能满足区间内每个数的出现次数为 k ？
思路：考虑用哈希来解决（详见代码）。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int a[200005];//更新 i 时的状态
map<int,int> mp,vis,ha;//mp记录 i 时的状态，ha 记录哈希值，vis标记这个数否出现过
map<int,vector<int>> pos;// pos 存这个数出现的位置
signed main()
{IOSint _;cin >> _;while(_--){mp.clear(),ha.clear(),vis.clear(),pos.clear();int n,k;cin >> n >> k;int l=0,ans=0;// l 是左端点，ans 记录答案 mp[0]++;// 初始状态 a[0]=0;// 初始化 for(int i=1;i<=n;i++){int x;cin >> x;if(!vis[x]){//若这个数没出现过，标记，并给定一个哈希值 vis[x]=1;ha[x]=rand()*rand()*rand()*rand()*rand();}pos[x].push_back(i);//将 x 出现的位置存起来 if(pos[x].size()>k){// 当这个数出现次数大于 k 次时，将窗口更改 while(l<pos[x][pos[x].size()-1-k]) mp[a[l++]]--;//左端点右移到 pos[x][pos[x].size()-1-k] 处，然后先删除状态再右移 }if(pos[x].size()%k==0) a[i]=a[i-1]-ha[x]*(k-1);//删除前面 k-1 个 x 造成的影响 else a[i]=a[i-1]+ha[x];// 不然直接加上这一状态 ans+=mp[a[i]];// 更新答案 mp[a[i]]++;// 状态记录 }cout << ans << endl;}return 0;
}
