小Q在进行射击气球的游戏，如果小Q在连续T枪中打爆了所有颜色的气球，将得到一只QQ公仔作为奖励。（每种颜色的球至少被打爆一只）。
这个游戏中有m种不同颜色的气球，编号1到m。
小Q一共有n发子弹，然后连续开了n枪。
小Q想知道在这n枪中，打爆所有颜色的气球最少用了连续几枪？
输入格式
第一行包含两个整数n和m。
第二行包含n个整数，分别表示每一枪打中的气球的颜色，0表示没打中任何颜色的气球。
输出格式
一个整数表示小Q打爆所有颜色气球用的最少枪数。
如果小Q无法在这n枪打爆所有颜色的气球，则输出-1。
数据范围
1≤n≤1061≤n≤106, 1≤m≤20001≤m≤2000
输入样例：
12 5 2 5 3 1 3 2 4 1 0 5 4 3输出样例：
6样例解释
有五种颜色的气球，编号1到5。
游客从第二枪开始直到第七枪，这连续六枪打爆了5 3 1 3 2 4这几种颜色的气球，包含了从1到5的所有颜色，所以最少枪数为6。
难度：中等时/空限制：1s / 64MB总通过数：87总尝试数：326来源：腾讯2019，笔试题
这道题目的思路是双指针滑窗。
#include <iostream> #include <algorithm> using namespace std; const int N = 100010; int arr[N]; int Hash[N]; // 用来记录数字出现次数 int main() { int n,m; cin>>n>>m; for(int i=0;i<n;i++) cin>>arr[i]; int count = 0; // 用来记录当前窗口内不同数出现的次数 int res = n; bool flag = false; for(int i=0,j=0;j<n;j++){ if(arr[j]!=0 && Hash[arr[j]]==0) count++; Hash[arr[j]]++; if(count == m){ flag = true; while(arr[i]==0 || Hash[arr[i]]>1){ Hash[arr[i]]--; i++; } res = min(res,j-i+1); } } cout<<(flag?res:-1)<<endl; system("pause"); }
