思路：双指针

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

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

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

代码

cpp

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

int main()
{
    int n, m;
    cin >> n >> m;

    vector<int> a(n + 1), b(m + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= m; ++i) cin >> b[i];

    int okc = 0;
    vector<int> cnt(m + 1);
    for (int i = 1; i <= m; ++i) if (b[i] == 0) okc += 1;

    int ans = n;
    for (int r = 1, l = 1; r <= n; ++r) {
        cnt[a[r]] += 1;
        if (cnt[a[r]] == b[a[r]]) okc += 1;
        while (l <= r && cnt[a[r]] >= b[a[r]]) {
            if (cnt[a[l]] - 1 >= b[a[l]]) {
                cnt[a[l]] -= 1;
                l += 1;
            } else {
                break;
            }
        }
        if (okc == m) {
            ans = min(ans, r - l + 1);
        }
    }

    if (okc < m) {
        cout << "-1\n";
    } else {
        cout << ans << "\n";
    }

    return 0;
}

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        int[] a = new int[n];
        int[] b = new int[m];
        
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        for (int i = 0; i < m; i++) {
            b[i] = sc.nextInt();
        }
        
        int result = findShortestSubarray(a, b, m);
        System.out.println(result);
        
        sc.close();
    }
    
    public static int findShortestSubarray(int[] a, int[] b, int m) {
        int n = a.length;
        
        // 用于存储需要满足的计数
        int[] requiredCounts = new int[m + 1];
        for (int i = 0; i < m; i++) {
            requiredCounts[i + 1] = b[i];
        }
        
        // 用于存储当前窗口的计数
        int[] currentCounts = new int[m + 1];
        int required = 0;
        for (int count : requiredCounts) {
            if (count > 0) {
                required++;
            }
        }
        
        int formed = 0;
        int left = 0;
        int minLength = Integer.MAX_VALUE;
        
        for (int right = 0; right < n; right++) {
            int num = a[right];
            if (num <= m) {
                currentCounts[num]++;
                
                if (requiredCounts[num] > 0 && currentCounts[num] == requiredCounts[num]) {
                    formed++;
                }
            }
            
            while (formed == required && left <= right) {
                int currentLength = right - left + 1;
                if (currentLength < minLength) {
                    minLength = currentLength;
                }
                
                int leftNum = a[left];
                if (leftNum <= m) {
                    currentCounts[leftNum]--;
                    
                    if (requiredCounts[leftNum] > 0 && currentCounts[leftNum] < requiredCounts[leftNum]) {
                        formed--;
                    }
                }
                
                left++;
            }
        }
        
        return minLength == Integer.MAX_VALUE ? -1 : minLength;
    }
}

python

n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

l = 0
cnt = {}
ans = float('inf')
def valid(cnt):
    for i, x in enumerate(b):
        if cnt.get(i+1, 0) < b[i]:
            return False
    return True

for i, x in enumerate(a):
    cnt[x] = cnt.get(x, 0) + 1
    while l < i and valid(cnt):
        ans = min(ans, i - l + 1)
        cnt[a[l]] -= 1
        l += 1
print(ans)

题目描述

有一个长度为 $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$ 次。 可以证明没有更短的区间满足了。