题目:
解法:定义左索引和右索引
1.先让右索引往右移,直到得到所有知识点为止;
2.然后让左索引向右移,直到刚刚能够得到所有知识点;
3.用右索引减去左索引更新答案,因为这是满足要求的子串。
4.不断重复1,2,3。直到搜索到最后,不论怎样都获得不了所有的知识点时跳出。
代码:
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
typedef long long ll;
#define INF 2147483647 int n;
int a[]; map <int,int> m; int main(){
int n;
cin >> n;
set <int> q;
for(int i = ;i < n; i++){
scanf("%d",&a[i]);
q.insert(a[i]);
// cout << a[i] << endl;
}
int num = q.size();
// cout << num << endl;
int res = INF; int sum = ;
int s = ;int t = ;
while(true){
while(t < n && sum != num){
if(m[a[t]] == )
sum++;
m[a[t]]++;
t++;
}
while(m[a[s]] > ){
m[a[s]]--;
s++;
if(m[a[s-]] == ){
sum--;
break;
}
}
if(sum < num-) break;
// cout << s << " " << t << endl;
res = min(res,t-s+);
} cout << res << endl;
return ;
}