题解 | 可匹配子段计数

解决方案：滑动窗口 + 哈希计数优化

这是一个经典的定长滑动窗口问题。

1. 预处理数组 b：使用哈希表（或数组，如果数值范围可控）记录数组 b 中每个数字出现的频率。
2. 维护窗口计数：在数组 a 上维护一个长度为 m 的窗口。记录窗口内每个数字出现的频率。
3. 维护匹配贡献度 (currentMatch)：
1. 当我们向窗口增加一个元素 x 时：如果窗口内 x 的数量仍然小于或等于 b 中 x 的数量，说明这个新加入的 x 贡献了一个有效匹配。当我们从窗口移除一个元素 y 时：如果窗口内 y 的数量原本小于或等于 b 中 y 的数量，说明移除它会损失一个有效匹配。
4. 计数：每移动一次窗口，检查 currentMatch 是否 <= k。

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用快读以应对大数据量
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());

        while (t-- > 0) {
            String[] nmk = br.readLine().split(" ");
            int n = Integer.parseInt(nmk[0]);
            int m = Integer.parseInt(nmk[1]);
            int k = Integer.parseInt(nmk[2]);

            int[] a = new int[n];
            String[] lineA = br.readLine().split(" ");
            for (int i = 0; i < n; i++) a[i] = Integer.parseInt(lineA[i]);

            int[] b = new int[m];
            String[] lineB = br.readLine().split(" ");
            Map<Integer, Integer> bCount = new HashMap<>();
            for (int i = 0; i < m; i++) {
                b[i] = Integer.parseInt(lineB[i]);
                bCount.put(b[i], bCount.getOrDefault(b[i], 0) + 1);
            }

            // 开始滑动窗口
            Map<Integer, Integer> windowCount = new HashMap<>();
            int currentMatch = 0;
            int validSubsegments = 0;

            // 初始化第一个长度为 m 的窗口
            for (int i = 0; i < m; i++) {
                int val = a[i];
                int countInWindow = windowCount.getOrDefault(val, 0);
                int countInB = bCount.getOrDefault(val, 0);

                if (countInWindow < countInB) {
                    currentMatch++;
                }
                windowCount.put(val, countInWindow + 1);
            }

            if (currentMatch >= k) validSubsegments++;

            // 滑动窗口向右移动
            for (int i = m; i < n; i++) {
                // 移除左侧元素
                int leftVal = a[i - m];
                int leftCount = windowCount.get(leftVal);
                if (leftCount <= bCount.getOrDefault(leftVal, 0)) {
                    currentMatch--;
                }
                windowCount.put(leftVal, leftCount - 1);

                // 加入右侧元素
                int rightVal = a[i];
                int rightCount = windowCount.getOrDefault(rightVal, 0);
                if (rightCount < bCount.getOrDefault(rightVal, 0)) {
                    currentMatch++;
                }
                windowCount.put(rightVal, rightCount + 1);

                if (currentMatch >= k) validSubsegments++;
            }

            System.out.println(validSubsegments);
        }
    }
}