描述
给你一个长度为n的数字串，数字串里会包含1-m这些数字。如果连续的一段数字子串包含了1-m这些数字，则称这个数字字串为NUM串。你的任务是求出长度最短的NUM串是什么，只需要输出这个长度即可。
1<=n，m<=200000
1<=n，m<=200000
输入格式
第一行给定n和m。
第二行n个数，表示数字串，数字间用空格隔开。
第二行n个数，表示数字串，数字间用空格隔开。
输出格式
如果存在NUM串则输出最短NUM串长度，否则输出“NO”。
测试样例1
输入
5 3
1 2 2 3 1
输出
3
代码
1 #include<iostream> 2 #include<cstring> 3 #include<algorithm> 4 #include<cstdio> 5 using namespace std; 6 int n,m,num[200005],a[200005],mn; 7 int cnt,l=0,r=1;//用两个指针，分别指向头和尾 8 9 void print(){ 10 for(int i=1;i<=m;i++) printf("%d ",num[i]); 11 puts(" "); 12 } 13 14 int main(){ 15 // freopen("01.txt","r",stdin); 16 scanf("%d%d",&n,&m); 17 cnt=m; 18 if(n<m){//n<m不可能有数字串 19 cout<<"NO"<<endl; 20 return 0; 21 } 22 for(int i=1;i<=n;i++) 23 scanf("%d",&a[i]); 24 25 for(;r<=n;r++){//尾后移 26 if(num[a[r]]==0) { 27 ++num[a[r]]; 28 --cnt; 29 } 30 else ++num[a[r]]; 31 if(cnt==0) break; 32 } 33 if(cnt>0){ 34 cout<<"NO"<<endl; 35 return 0; 36 } 37 38 mn=r-l;//l此时为0 39 while(l<=n){//头后移 40 ++l; 41 // printf("l=%d r=%d ",l,r); 42 // print(); 43 if(num[a[l]]==1) --num[a[l]],++cnt; 44 else --num[a[l]]; 45 // cout<<cnt<<endl; 46 if(cnt==0) {mn=min(mn,r-(l+1)+1);continue;} 47 48 ++r; 49 for(;r<=n;++r){ 50 if(num[a[r]]==0) ++num[a[r]],--cnt; 51 else ++num[a[r]]; 52 if(cnt==0) break; 53 } 54 if(cnt) break; 55 else mn=min(mn,r-(l+1)+1); 56 } 57 printf("%d ",mn); 58 return 0; 59 }cnt用于记录当前是否还需要添加元素