解题思路

题意：给定长度为 $n$ 的货位序列，每个位置放一种商品（编号从 1 开始）。再给出 $m$ 个要求数组 $b[1..m]$，表示第 $x$ 类商品在区间内至少出现 $b_x$ 次。求满足所有要求的最短连续区间长度，不存在则输出 -1。

核心算法：双指针滑动窗口

1. 只关心 $b_x>0$ 的品类，其余视为无需约束。

2. 先做一次可行性预检：统计整段序列每个品类的总次数 total[x]，若存在 total[x] < b[x]（且 b[x]>0），则必无解，直接输出 -1。

3. 使用左右指针维护当前窗口 [l, r]，并用 cnt[x] 统计窗口内每个品类出现次数。

   • 右指针右移扩张窗口，若某类第一次达到需求（cnt[x]==b[x] 且 b[x]>0），则把“已满足的品类数” sat 加一。
   • 当 sat 等于“需要的品类数” needKinds 时，尝试左移 l 贪心缩小：只要移走左端商品不会让该类小于需求（cnt[a[l]]-1 >= b[a[l]]），就移动并更新计数。记录最小长度。

4. 特判：如果所有 $b_x=0$，任意单点即可，答案为 1。

实现要点

• 计数数组大小取 max(m, max(a))，对编号超过 m 的商品，将其需求视为 0。
• 维护变量：needKinds（有正需求的品类数）、sat（当前满足的品类数）、ans（最小长度）。

复杂度分析

• 时间复杂度：$O(n+m)$。每个指针最多走一遍；预检一次遍历。
• 空间复杂度：$O(K)$，其中 $K=\max(m,\max(a))$（计数与需求数组）。

代码实现

Python

# 题面功能在函数中，输入输出在主函数（ACM风格）

import sys

def shortest_interval(n, m, arr, need_input):
    # 计算编号上界，容纳可能大于 m 的商品编号
    max_id = max(max(arr), m)
    need = [0] * (max_id + 1)
    for i in range(1, m + 1):
        need[i] = need_input[i - 1]

    # 预检：整段统计
    total = [0] * (max_id + 1)
    for x in arr:
        if x <= max_id:
            total[x] += 1
    for i in range(1, max_id + 1):
        if need[i] > 0 and total[i] < need[i]:
            return -1

    # 需要的品类数
    needKinds = sum(1 for i in range(1, max_id + 1) if need[i] > 0)
    if needKinds == 0:
        return 1  # 任意一个位置即可

    cnt = [0] * (max_id + 1)
    sat = 0
    ans = n + 1
    l = 0

    for r in range(n):
        x = arr[r]
        cnt[x] += 1
        # 刚好达到需求时，已满足品类 +1（只对 b[x] > 0 生效）
        if need[x] > 0 and cnt[x] == need[x]:
            sat += 1

        # 已满足所有需求，尝试收缩左端
        while sat == needKinds:
            # 更新答案
            curr_len = r - l + 1
            if curr_len < ans:
                ans = curr_len
            # 能否安全移走左端？
            y = arr[l]
            if cnt[y] - 1 >= need[y]:
                cnt[y] -= 1
                l += 1
            else:
                break

        # 若仍满足，继续移走左端元素（确保最短）
        while sat == needKinds:
            y = arr[l]
            if cnt[y] - 1 >= need[y]:
                cnt[y] -= 1
                l += 1
                ans = min(ans, r - l + 1)
            else:
                break

        # 若移走会破坏需求，则等待下次扩张
        if sat == needKinds:
            # 尝试移走一次并更新 sat
            y = arr[l]
            cnt[y] -= 1
            l += 1
            if need[y] > 0 and cnt[y] == need[y] - 1:
                sat -= 1

    return -1 if ans == n + 1 else ans


def main():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    n = int(next(it)); m = int(next(it))
    arr = [int(next(it)) for _ in range(n)]
    need_input = [int(next(it)) for _ in range(m)]
    print(shortest_interval(n, m, arr, need_input))

if __name__ == "__main__":
    main()

Java

// 类名必须为 Main，ACM 风格：主函数做输入输出，功能在外部静态函数
import java.io.*;
import java.util.*;

public class Main {

    // 快读（数据量较大时更稳）
    static class FastScanner {
        private final InputStream in;
        private final byte[] buffer = new byte[1 << 16];
        private int ptr = 0, len = 0;
        FastScanner(InputStream is) { in = is; }
        private int read() throws IOException {
            if (ptr >= len) {
                len = in.read(buffer);
                ptr = 0;
                if (len <= 0) return -1;
            }
            return buffer[ptr++];
        }
        int nextInt() throws IOException {
            int c, sgn = 1, x = 0;
            do { c = read(); } while (c <= ' ');
            if (c == '-') { sgn = -1; c = read(); }
            while (c > ' ') { x = x * 10 + (c - '0'); c = read(); }
            return x * sgn;
        }
    }

    // 题面功能实现：返回最短长度，不存在返回 -1
    static int shortestInterval(int n, int m, int[] arr, int[] needIn) {
        int maxId = m;
        for (int x : arr) if (x > maxId) maxId = x;

        int[] need = new int[maxId + 1];
        for (int i = 1; i <= m; i++) need[i] = needIn[i - 1];

        // 预检：整段统计
        int[] total = new int[maxId + 1];
        for (int x : arr) total[x]++;
        for (int i = 1; i <= maxId; i++) {
            if (need[i] > 0 && total[i] < need[i]) return -1;
        }

        int needKinds = 0;
        for (int i = 1; i <= maxId; i++) if (need[i] > 0) needKinds++;
        if (needKinds == 0) return 1;

        int[] cnt = new int[maxId + 1];
        int sat = 0, ans = n + 1;
        int l = 0;

        for (int r = 0; r < n; r++) {
            int x = arr[r];
            cnt[x]++;
            if (need[x] > 0 && cnt[x] == need[x]) sat++;

            while (sat == needKinds) {
                ans = Math.min(ans, r - l + 1);
                int y = arr[l];
                if (cnt[y] - 1 >= need[y]) {
                    cnt[y]--;
                    l++;
                } else {
                    break;
                }
            }

            if (sat == needKinds) {
                int y = arr[l];
                cnt[y]--;
                l++;
                if (need[y] > 0 && cnt[y] == need[y] - 1) sat--;
            }
        }
        return ans == n + 1 ? -1 : ans;
    }

    public static void main(String[] args) throws Exception {
        FastScanner fs = new FastScanner(System.in);
        int n = fs.nextInt(), m = fs.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = fs.nextInt();
        int[] need = new int[m];
        for (int i = 0; i < m; i++) need[i] = fs.nextInt();
        int ans = shortestInterval(n, m, arr, need);
        System.out.println(ans);
    }
}

C++

// ACM 风格：主函数读写，核心功能放在外部函数
#include <bits/stdc++.h>
using namespace std;

// 返回最短区间长度，不存在返回 -1
int shortestInterval(int n, int m, const vector<int>& a, const vector<int>& needIn) {
    int maxId = m;
    for (int x : a) maxId = max(maxId, x);

    vector<int> need(maxId + 1, 0);
    for (int i = 1; i <= m; ++i) need[i] = needIn[i - 1];

    // 预检：整段统计
    vector<int> total(maxId + 1, 0);
    for (int x : a) total[x]++;
    for (int i = 1; i <= maxId; ++i) {
        if (need[i] > 0 && total[i] < need[i]) return -1;
    }

    int needKinds = 0;
    for (int i = 1; i <= maxId; ++i) if (need[i] > 0) needKinds++;
    if (needKinds == 0) return 1;

    vector<int> cnt(maxId + 1, 0);
    int sat = 0, ans = n + 1;
    int l = 0;

    for (int r = 0; r < n; ++r) {
        int x = a[r];
        cnt[x]++;
        if (need[x] > 0 && cnt[x] == need[x]) sat++;

        // 收缩左端，尽可能短
        while (sat == needKinds) {
            ans = min(ans, r - l + 1);
            int y = a[l];
            if (cnt[y] - 1 >= need[y]) {
                cnt[y]--;
                l++;
            } else break;
        }

        // 若仍满足，尝试移走一个以继续扩展
        if (sat == needKinds) {
            int y = a[l];
            cnt[y]--;
            l++;
            if (need[y] > 0 && cnt[y] == need[y] - 1) sat--;
        }
    }
    return (ans == n + 1) ? -1 : ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    vector<int> need(m);
    for (int i = 0; i < m; ++i) cin >> need[i];

    cout << shortestInterval(n, m, a, need) << "\n";
    return 0;
}

题目内容

某超市要对一批货架上的商品进行备货检查。货架上共有 $n$ 个连续的货位(编号 $1$ 到 $n$ )，每个货位上放置着一种商品。当前超市有 $m$ 类商品(编号 $1$ 到 $m$ )，其中第 $x$ 类商品要求在检查区间内至少出现 $b_x$ 次 ($b_x$ 为非负整数)。

请找出长度最短的连续货位区间 $[l,r]$ ，使得该区间内 $1$ 到 $m$ 类商品的出现次数均满足上述要求。我们定义区间长度为 $r-l+1$ 。若不存在这样的区间，输出 $-1$ 。

输入描述

第一行包含两个整数 $n$ 和 $m(1≤n,m≤10^5)$ ，分别表示货位总数和商品的类别数。

第二行包含 $n$ 个整数，依次表示每个货位上的商品编号。

第三行包含 $m$ 个整数，依次表示第 $1$ 到 $m$ 类商品的最低出现次数要求( $b_1$ 到 $b_m$ ) 。

保证商品编号为不超过 $10^5$ 的非负整数。

输出描述

输出一个整数，表示满足要求的最短区间长度；

若不存在，输出 $-1$ 。

样例1

输入

10 4
3 1 2 1 3 4 2 1 3 2
2 1 0 1

输出

5

说明

重点监拉的 $4$ 类商品要求：

商品 $1$ ：至少出现 $2$ 次；

商品 $2$ ：至少出现 $1$ 次；

商品 $3$ ：至少出现 $0$ 次（无要求）；

商品 $4$ ：至少出现 $1$ 次。

其中一种符合要求的最短区间是 $[4,8]$ (商品序列为 $[1,3,4,2,1]$，长度为 $5$ 。