本文主要是介绍Codeforces Round 938 (Div. 3)------＞D. Inaccurate Subsequence Search，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一，思路：
1.这是一道很明显的双指针问题（类滑窗问题），我们只需要用一个双指针在a数组中维护一个长度为m区间，同时维护当中与b数组中匹配的数量 cnt，那么怎么维护呢？
2.一个一个遍历肯定不行的，我们可以发现一个性质，就是随着区间移动，他只有首位的数子发生变化，所以我们只需要判断首位的数字匹配情况，来更新cnt,这样就能实现O(n)的时间复杂度来解决。
二，代码：
#include <iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#include<stack>
#include<queue>
#include<map>
#include<vector>
using namespace std;const int N=2e5+10,M=1e9+7;typedef long long ll;
typedef pair<int,int> pii;int arr[N],brr[N];void Solved() {int n,m,k;cin>>n>>m>>k;for(int i=1;i<=n;i++){cin>>arr[i];}//记录b数组中数字情况（注意有重复的情况）map<int,int> mp;for(int i=1;i<=m;i++){cin>>brr[i];mp[brr[i]]++;}//维护长度为m的区间的数字情况map<int,int> temp;int res=0;int cnt=0;for(int r=1,l=1;r<=n;r++){//右端点的移动可以使区间内的数字数量增加 temp[arr[r]]++;//对于这个判断的原因我举个例子你就明白了
//当区间中已经有两个一样的数字2与b数组匹配，那么此时再增加一个数字2，也不会改变匹配数量
//反之如果 temp[arr[r]]<=mp[arr[r]]说明“坑位”还有，可以贡献匹配数if(temp[arr[r]]<=mp[arr[r]]) cnt++;//左端点的移动会使区间内数字减小
//和右端点移动一样的道理，加入区间内有3个2，但是b数组中只有2两个2，此时你2减少一个也不会影响匹配数if(r>m) {temp[arr[l]]--;if(temp[arr[l]]<mp[arr[l]]) cnt--;l++;}//起始区间也要算进去（r==m）的时候if(r>=m&&cnt>=k) res++;}cout<<res<<endl;
}int main()
{int t;cin>>t;while(t--) {Solved();}return 0;
}这篇关于Codeforces Round 938 (Div. 3)------＞D. Inaccurate Subsequence Search的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
