题目描述

本题的题意很简单，找出最短的包含所有颜色的气球的区间。本题属于非常经典的题，采用双指针算法。本题需要设置一个flag，即当凑齐给定要求的神龙的时候，才可以计算区间长度。

计算区间长度的时候，需要考虑慢指针指向位置处是不是重复元素，是的话，需要删除。

需要注意到0元素的存在，慢指针如果指向0元素，则需要将i++；

每次计算完当前区间的长度的时候，需要将当前的i值++，伴随的操作的是将该值出现的此–。这么做是为了将区间后移。假设不进行此操作，那么一旦出现一次满足要求的区间，其后的所有区间都是满足要求的，不合理也不对。

算法1

(双指针) $O(n)$

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;


int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> input(n, 0);
    unordered_map<int,int> tmp;
    for(int i = 0; i < n; i ++ ) cin >> input[i];
    int res = 1e6 + 10; 
    int ColorNums = 0;
    for(int i = 0, j = 0; j < n; j ++ )
    {
        int t = input[j];
        if(t == 0) continue;
        else if(tmp[t] == 0){
            ColorNums ++;
            tmp[t] ++;
        }else tmp[t] ++;

        if(ColorNums == m)
        {
            for(; i < j; )
            {
                t = input[i];
                if(tmp[t] > 1)  {
                    tmp[t]--;
                    i ++ ;
                }
                else if(t == 0) i ++ ;
                else break;
            }
            res = min(res, j - i + 1);
            tmp[t] -- ;
            i ++ ;
            ColorNums -- ;
        }
    }

    if(res == 1e6 + 10) cout << -1 << endl;
    else cout << res << endl;

    return 0;
}