题目描述
小明有一个n个整数的数组a和一个m个整数的数组b(m<=n)
如果数组c中的元素可以重新排列,使其中至少有k个元素与数组b中的元素匹配,那么小明认为长度为m的数组c是好数组
例如,如果b(b=[1,2,3,4])和k(k=3),那么数组[4,1,2,3]和[2,3,4,5]就是好数组(他们可以重新排列如下:[1,2,3,4]和[5,2,3,4]),而数组[3,4,5,6]和[3,4,3,4]则不是好数组
小明想选择数组a中长度为m的每个子段作为数组c的元素
换句话说,求1<=l<=n-m+1的位置数,使得元素al,al+1,…al+m-1组成一个好数组
样例
input
5
7 4 2
4 1 2 3 4 5 6
1 2 3 4
7 4 3
4 1 2 3 4 5 6
1 2 3 4
7 4 4
4 1 2 3 4 5 6
1 2 3 4
11 5 3
9 9 2 2 10 9 7 6 3 6 3
6 9 7 8 10
4 1 1
4 1 5 6
6
output
4
3
2
4
1
算法1
窗口滑动
#include <iostream>
//#include <bits/stdc++.h>
#include <string>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <set>
#include <map>
#include <vector>
#include <deque>
#include <iomanip>
#include <queue>
#include <utility>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
//deque<int> q;
const int N = 1e6 + 10;
int a[N], b[N], c[N], d[N];
int main()
{
int t;
cin >> t;
while (t--)
{
int n, m,k;
cin >> n >> m>>k;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++)
{
cin >> b[i];
c[b[i]]++;//统计b数组中的个数
}
int ans = 0, now = 0;//now代表窗口内有几个元素可以和b数组匹配
for (int i = 1; i <= n; i++)//窗口滑动,c[]代表b数组元素个数,d[]代表窗口元素个数,每个数字只能匹配一次,不能一个数组的4同时匹配另外一个数组的两个4,每当被窗口滑出一个匹配好的数字,新进入窗口的数字如果能匹配b数组中的数字,则加一
{
if (d[a[i]] < c[a[i]]) now++;//当前的a[i]可以和b数组匹配
d[a[i]]++;//窗口元素加一,这样的操作可以避免一个数字同时匹配更多数字
if (i - m >= 1)//滑动
{
d[a[i - m]]--;//元素被滑出窗口
if(d[a[i - m]] < c[a[i - m]]) now--;//如果他是与b匹配的元素,被滑出了,now-1
}
if (i >= m && now >= k) ans++;
}
cout << ans << endl;
for (int i = 1; i <= n; i++) d[a[i]] = 0;//归零
for (int i = 1; i <= m; i++) c[b[i]] = 0;
}
return 0;
}
算法2
双端队列
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=2e5+10;
int a[N],b[N];
int n,m,k;
void solve() {
cin>>n>>m>>k;
for(int i=1;i<=n;i++) cin>>a[i];
map<int,int>target;
for(int i=1;i<=m;i++) cin>>b[i],target[b[i]]++;
int match=0;
int ans=0;
deque<int>q;
map<int,int>mp;//——————————————————这部分的代码可以算出两个数组内有几个相同的数可以匹配,比如1,2,3,4和3,4,3,4算出的数字是2
for(int i=1;i<=m;i++){
q.push_back(a[i]);
if(mp[a[i]]<target[a[i]]){
if(target[a[i]]){
match++;
}
}
mp[a[i]]++;
}
if(match>=k) ans++;
for(int i=m+1;i<=n;i++){
if(mp[q.front()]<=target[q.front()]){
if(target[q.front()]) match--;
}
mp[q.front()]--;
q.pop_front();
q.push_back(a[i]);
if(mp[a[i]]<target[a[i]]){
if(target[a[i]]) match++;
}
mp[a[i]]++;
if(match>=k) ans++;
}
cout<<ans<<endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
cin>>t;
while(t--) {
solve();
}
return 0;
}