对于此题,双指针来写很显然会超时:)
(亲身经历)
Code(c++)–[双指针]【很显然这种方法我不想再追究】
#include<iostream>
#include<map>
using namespace std;
const int maxn=1e6+10;
int n,m,ai[maxn],p,q,ans=maxn,ansx,ansy;
map<int,int> cnt;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>ai[i];
p=1;
q=0;
while(cnt.size()!=m)q++,cnt[ai[q]]++;
ans=q-p+1;
ansx=p;
ansy=q;
while(q<=n && p<=n){
cnt[ai[p]]--;
if(cnt[ai[p]]==0){
cnt.erase(cnt.find(ai[p]));
while(q<n && cnt.size()!=m)q++,cnt[ai[q]]++;
if(cnt.size()!=m)break;
}
p++;
if(q-p+1<ans)ans=q-p+1,ansx=p,ansy=q;
}
cout<<ansx<<' '<<ansy<<endl;
}
qwq
所以,我们只能另辟其径Σ(っ °Д °;)っ
CODE(C++)
#include<iostream>
//#include<cmath>
//#inlcude<map>
using namespace std;
int q[10000005],id[1000005],tong[1000005];
int main() {
int n,m;
cin >> n>>m;
for(int i=1; i<=n; i++) cin >> id[i];
int minlen =n,a,b;
int nums=0;
int head=1,tail=0;
tail++;
q[tail] = id[tail];
tong[id[tail]] ++;
nums++;
while (head<=tail) {
if(nums == m) {
if(minlen > tail - head+1) {
minlen = tail -head+1;
a=head;
b=tail;
}
tong[id[head]]--;
if(tong[id[head]] ==0)nums--;
head++;
}else if(tail < n){
tail++;
q[tail] = id[tail];
if (tong[id[tail]]==0) nums++;
tong[id[tail]]++;
}
if (tail == n && nums < m) break;
}
cout <<a << " " << b << endl;
}
图不错^^