数据结构算法——1016. 欣赏书法

题目

in
10 5
1 4 5 4 2 5 4 1 3 5
out
5 9

思路

用队列，先不断push进去，同时用一个数组记录每个大师作品在这个队列中的数量，再用一个常量size记录多少个大师已经在queue里面了
当size == m的时候就进行出列操作，直到遇见有一个大师作品完全出队列了，这个时候size–，我们就可以把相对来说最短的一个队列拿出来赋值给l和r，这个时候left下标对应的数组元素是0，所以别忘记++left

代码

#include<iostream>
#include<bits/stdc++.h>
using namespace std;int main()
{int n,m;cin >> n >> m;int* master = new int[m];for(int i = 0; i < m; i++)master[i] = 0;int* piece = new int[n];for(int i = 0; i < n; i++)cin >> piece[i];//store piece of masterint left = 0, right = -1;int count = 0;int l = left , r = right;int maxn = INT_MAX;while(right < n){right++;if(right == n) break;if(master[piece[right] - 1] == 0){count++;//入列}master[piece[right] - 1]++;//记录次数if(count == m){   while(master[piece[left] - 1] > 0){master[piece[left] - 1]--;//出列if(master[piece[left] - 1] == 0){count--;break;}left++;}if(right - left < maxn){maxn = right - left;l = left;r = right;}left++;//别忘记下标这个数已经清零了然而下标没更新}// cout << l + 1 << " " << r + 1 << endl;// for(int i = 0; i < m; i++)//     cout << master[i] <<" ";// cout << endl;}if(r < 0){    r++;}cout << l + 1 << " " << r + 1 << endl;
}