尺取法

尺取法经典例题

#include <bits/stc++.h>
using namespace std;

const int MAX_P = 1e6+7;
int P;
int a[MAX_P];

void solve(){
    set<int> all;
    for (int i = 0;i < P;i ++){
        all.insert(a[i]);
    }
    int n = all.size();

    int s = 0,t = 0,num = 0;
    map<int,int> count;// 知识点->出现的次数
    int res = P;
    for (;;){
        while (t < P && num < n){
            if (count[a[t++]] ++ == 0){
                // 出现新的知识点
                num ++;
            }
        }
        if (num < n) break;
        res = min(res,t-s);
        if (--count[a[s++]] == 0){
            //某个知识点出现的次数为0了
            num --;
        }
    }
    printf("%d\n",res);
}

int main()
{
    scanf("%d",&P);
    for (int i = 0;i < P;i ++)scanf("%d",&a[i]);

    solve();
}

超级无敌简洁的代码