题目链接：https://nanti.jisuanke.com/t/15768
解析：一直尺取，记录相同的个数，复杂度O(n)
代码：
#include<bits/stdc++.h> #define N 50009 using namespace std; const int INF = 0x3f3f3f3f; int a[N], b[N], c[N]; int judge(int n, int nn, int mx) { int ans = 0, x = 0; memset(c, 0, sizeof(c)); for(int i = 1; i <= nn; i++) { c[a[i]]++; if(c[a[i]] == b[a[i]]) x++; if(c[a[i]] - 1 == b[a[i]] && b[a[i]]) x--; } if(x == mx) ans++; for(int i = nn + 1; i <= n; i++) { c[a[i]]++; if(c[a[i]] == b[a[i]]) x++; if(c[a[i]] - 1 == b[a[i]] && b[a[i]]) x--; c[a[i-nn]]--; if(c[a[i-nn]] == b[a[i-nn]] && b[a[i-nn]]) x++; if(c[a[i-nn]] + 1 == b[a[i-nn]]) x--; if(x == mx) ans++; } return ans; } int main() { int n, m; scanf("%d", &n); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); scanf("%d", &m); while(m--) { int num, nn, mx = 0; memset(b, 0, sizeof(b)); scanf("%d", &nn); for(int i = 1; i <= nn; i++) { scanf("%d", &num); if(!b[num]) mx++; b[num]++; } printf("%d\n", judge(n, nn, mx)); } return 0; }
