题目描述

将题目转化为求解包含1~m所有元素的最短区间

题目分析

利用双指针和滑动窗口思想：
利用指针i遍历整个数组，如果第一次遍历到某元素，则将在区间中的元素的cnt值加一
当整个区间包含所有元素时，将j向前移动，缩小区间长度，更新结果

代码示例

#include<iostream>

using namespace std;

const int N = 1E6 + 10, M = 2010;

int a[N], cnt[M];
int n, m;

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

    int colors = 0;
    int res = n + 1;
    for(int i = 1, j = 1; i <= n; i++)
    {
        if(a[i] && !cnt[a[i]]) colors++; //该位不为零且未在包含区间中
        cnt[a[i]]++; //该元素数目加一

        if(colors == m) //区间包含所有元素
        {
            while(!a[j] || cnt[a[j]] > 1)  //该位为零或区间中该数字多余
            {
                cnt[a[j]]--;
                j++;
            }
            res = min(res, i - j + 1); //更新结果
        }
    }

    if(res > n) res = -1;
    cout<<res<<endl;
    return 0;

}