洛谷 P1638 逛画展

 此题运用滑动窗口和左右指针

1.用identifiers储存画师的编号

2.用count储存画师的画的数量

3.将左右指针初始化为0，先右移右指针，当恰好找到第一个解时（即左右指针范围内画师数量恰好等于m），进入下一个while，如果此时窗口长度小于前一个解的窗口长度，相等则取左指针较靠前的。

4.移动左指针，收缩窗口

注：

1.将end_right初始化为n，表示窗口的右边界位于数组之外的位置，方便后续if判断更新值

2.先更新最优解，再收缩窗口，防止错过最优解

3.输出的end_left要+1，因为C++的数组下标从0开始，题目的a从1开始

#include <bits/stdc++.h>
using namespace std;
int main(void){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n,m,x;
    cin>>n>>m;
    vector <int> identifiers;
    //滑动窗口，左右指针
    for (int i=0;i<n;i++){
        cin>>x;
        identifiers.push_back(x); //画师的编号
    }
    vector <int> count(m+1,0); //画师的画的数量
    int painter=0,left=0,right=0,end_left=0,end_right=n;
    while (right<n){ //右指针指向indentifiers中画师的编号再指向画师画的数量
        if (count[identifiers[right]]==0){
            painter++;//如果该画师画的数量为0（第一次出现），增加画师数量
        }
        count[identifiers[right]]++;//增加画师画的数量
        right++;//右指针右移
    //如果此时画师数量恰好最大，说明找到了第一个解
    while (painter==m&&left<right){
        if ((right-left<end_right-end_left)||(right-left==end_right-end_left&&left<end_left)){
            end_left=left;
            end_right=right;
        }
        count[identifiers[left]]--;
        if (count[identifiers[left]]==0){
            painter--;
        }
        left++;
        }
    }
    cout<<end_left+1<<" "<<end_right;
}