算法题（136）：逛画展

审题：
本题需要我们找出区间元素最少的，包含（1~m）编号的区间左边界和右边界

思路：
方法一：暴力搜索

我们可以对每一个子段进行双重for循环搜索，然后用mp数组和kind变量来判断是否满足包含1~m所有编号的条件，若满足就进行区间缩小，缩小后根据区间大小判断是否保存边界

时间复杂度为：O（n*n），而n最大为1e6，所以循环次数为1e12,一定超时

方法二：双指针（滑动窗口）

我们可以让right指针不回退，然后用mp数组维护left和right之间的区间。就而只进行一次遍历，将时间复杂度降低为O(n)

解题：
（1）变量定义

#include<iostream>
using namespace std;
int n, m;
const int N = 1e6 + 10;
int a[N];
int kind;//记录无重复数据个数
int mp[N];//记录i在区间内出现次数
pair<int, int> pos(1,N);//维护边界

kind：当该编号是第一次进入区间的时候，也就是mp[a[right]] == 0，此时我们就让kind++

pair类型的变量pos可以用于记录边界值

（2）main函数

int main()
{//数据录入cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];}//进行搜索int left = 1;for (int right = 1; right <= n; right++){if (mp[a[right]] == 0)//新的编号进入区间{	kind++;}mp[a[right]]++;while (kind == m){mp[a[left]]--;if (mp[a[left]] == 0) kind--;//更新边界值if (kind == m - 1){int oldsize = pos.second - pos.first + 1;if (right - left + 1 < oldsize){pos.first = left;pos.second = right;}}left++;}	}cout << pos.first << " " << pos.second << endl;return 0;
}

注意：
1.更新时机：在缩短区间刚好使kind减为m-1的时候我们进行边界更新判断，不同的题目更新时机会有所不同

2.由于size一样的时候我们保留左边界更小的，也就是更早更新的边界，所以我们的边界更新条件就变成了新的size小于oldsize才更新

P1638 逛画展 - 洛谷