思路：双指针

考虑双指针，枚举右端点，移动左端点，直到如果左端点被删除后不满足条件时，则停止。

更新答案时，需要考虑是否每个 $x\in [1, m]$ 都有至少 $b[x]$ 个，可以用一个变量来统计达到最低数量的数的个数。

时间复杂度：$O(n)$

代码

cpp

题目描述

塔子哥有一个长度为 $n$ 的数组 $a$ 和 长度为 $m$ 的数组 $b$ ，下标均从 $1$ 开始。

现在，塔子哥想让你找出一个最短的区间 $[l, r] (1\leq l\leq r\leq n)$ ， 这个区间中数 $x$ 的数量至少出现了 $b[x]$ 次。

输入描述

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

输出描述

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

样例

输入

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

输出

5

说明

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