塔子哥的最短区间-小米2023笔试(codefun2000)

题目链接
塔子哥的最短区间-小米2023笔试(codefun2000)

题目内容

塔子哥有一个长度为 n 的数组 a 和 长度为 m 的数组 b ，下标均从 1 开始。
现在，塔子哥想让你找出一个最短的区间 l,r ， 这个区间中数 x 的数量至少出现了 b[x] 次。

输入描述

第一行，两个整数 n,m( 1 ≤ n , m ≤ 1 0 5 1≤n,m≤10^5 1≤n,m≤105 ) 分别表示数组 a 和数组 b 的长度。
第二行，n 个整数表示数组 a 。
第三行，m 个整数表示数组 b 。

输出描述

一个整数，表示最短区间的长度，如果不存在，则输出 -1 。

样例1

输入

6 4
1 1 4 5 1 4
2 0 0 2

输出

5

提示

区间 [2,6] 满足 1 和 4 出现了至少两次，2 和 3 出现了至少 0 次。 可以证明没有更短的区间满足了。

题解1

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int n, m, a[N], b[N], cnt[N]; // cnt[i]表示i出现的次数 

bool check(int x){ // 当前枚举的区间长度为x 
	memset(cnt, 0, sizeof cnt);
	for(int i = 1; i <= n; i++){ 
		cnt[a[i]]++;// 双指针
		if(i >= x){  
			int j = 1;
			while(j <= m && cnt[j] >= b[j]) j++;
			if(j > m) return true;
			cnt[a[i - x + 1]]--;
		}
	}
	return false;
}
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for(int i = 1; i <= m; i++) scanf("%d", &b[i]);
	
	int left = - 1, right = n + 1, mid;
	while(left + 1 < right){ // 二分枚举满足条件的最小区间的长度 
		mid = (left + right)/2;
		if(check(mid)) right = mid;
		else left = mid;
	}
	printf("%d\n", check(right)?right:-1);
	return 0;
}