备战蓝桥杯：双指针（滑动窗口）算法之逛花展

P1638 逛画展 - 洛谷 | 计算机科学教育新生态

这道题我们只要用一个kind和一个mp[N]的数组就能解决了

我们的解法1就是暴力枚举，先固定2，从2开始找连续的满足所有种类的最短的子数组，然后固定5，3，1，3，2，分别找出满足所有种类的最短子数组

mp[i]如果是从0到1，kind++，如果是从1到0，kind--

如图，暴力枚举的话j指向的一定是第一次出现的最新的元素种类，如果我们是暴力枚举的话，我们枚举5的时候，j也会回到5

我们对5枚举的时候，j一定会再走到4那个位置，我们何必让j回退呢？

那我们的算法流程就是用left和right指针指向第一个元素，然后让right指针向后走把每个元素进窗口，如果kind种类够了的话，left不断++，再不断更新每个合法的子数组的大小，直到kind不够了再退出去继续right向后走

比如这是一种结果，2出窗口后又是一个结果 

5出窗口后种类不够了，j向后走

不满足要求就不更新结果直到再次符合要求，我们再次让left出窗口

到这里把3出窗口之后再次成为不合法数组

再次合法，继续出left，出了一个就不合法了，right向后走一格，结束

我们来展示一下代码

#include <iostream>
using namespace std;

const int N = 1e6+10;
int n,m;
int mp[N];
int a[N];
int main()
{
	cin >> n  >> m;
	for(int i = 1;i<=n;i++) cin >> a[i];
	
	int kind = 0;
	int left = 1 , right = 1;
	int ret = n,begin = 1;
	while(right<=n)
	{
	    if(mp[a[right]]++ == 0) kind++;
		while(kind == m)
		{
		    int len = right-left+1;
		    if(len < ret)
		    {
		    	ret = len;
		    	begin = left;
			}
		    if(mp[a[left]]-- == 1) kind--;
		    left++;
		}	
		right++;
	}
	cout << begin <<" " << begin+ret-1<< endl;
       	
	
	
	
	
	
	
	
	return 0;
}