题解 | #Go to Play Maimai DX#
Go to Play Maimai DX
https://ac.nowcoder.com/acm/contest/57359/G
第G题题解
题目意思：
第一行输入n和k，代表该数组长度为n，至少包含k个4；
第二行输入数组（每个数字大于等于1，小于等于4）；
求最短的区间长度至少包含1个1，1个2，1个3和k个4。
思路：
类似利用双指针l和r，先让终点从开始一直往后，直到找到一个区间满足题目条件，接着缩短起点的位置，让起点在满足条件的情况下不断靠近终点
#include<bits/stdc++.h>
using namespace std;
int ans=1e9;
int a[100005];
int main(){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++) cin>>a[i];
int l=1,r=1;
map<int,int> mp; //类似字典
while(l<=r&&r<=n)
{
if(r!=n+1) mp[a[r]]+=1;
while(mp.size()==4&&mp[4]>=k&&l<=n) //当字典中存在1，2，3，4种键，并且键4的值满足k个
{
ans=min(ans,r-l+1);
mp[a[l]]-=1; //因为起点要不断靠近终点，所以当前存下来的值会被削减
if(mp[a[l]]==0) mp.erase(a[l]);
l++;
}
r++;
}
cout<<ans;
}
