思路：双指针

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

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

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

代码

1000ms

Difficulty: 5

算法与标签>双指针

有一个长度为 $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

输出

说明

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

输入

预期输出（选填）