G.Go to Play Maimai DX

区间问题

题目大意

给定一个长度为 $nn$ 仅含有 $1,2,3,41,2,3,4$ 四种数字的序列

求最短的包含 $1,2,31,2,3$ 和 $kk$ 个 $44$ 的区间的长度

解题思路

用快慢指针确定区间

快指针每次记录元素，直到满足条件；

慢指针每次移除元素，直到不满足条件

即可得到每个满足条件的最小区间，比较长度即可

时间复杂度

$O(n)O(n)$

参考程序

#define N 100005
int v[N]={0};
void solve()
{
	ll n,k;cin >> n >> k;
    FORLL(i,1,n) cin >> v[i];
    ll l=0,r=0,cnt[5]={0},re=n;
    while(r<=n){
        while(!(cnt[1]&&cnt[2]&&cnt[3]&&cnt[4]>=k)){
            r++;cnt[v[r]]++;if(r>n) break;
        }
        while(cnt[1]&&cnt[2]&&cnt[3]&&cnt[4]>=k){
            l++;cnt[v[l]]--;if(l>r) break;
        }re=min(re,r-l+1);
    }cout << re << endl;
}