题解 | 可匹配子段计数

import java.util.*;

import java.io.*;
import java.math.*;

// 整个题的思路就是A中所有长为M的子数组 公共元素频数之和是否>=K
// 滑动窗口A。长度为M。
// 每轮统计频数 与K 比较
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(new BufferedInputStream(System.in));
        PrintWriter out = new PrintWriter(System.out);
        int t = in.nextInt();
        while (t-- > 0) {
            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();
            int[] nums = new int[n + 1];
            //每轮窗口公共元素频数之和
            int res = 0;
            //最终答案
            int ans = 0;
            //数组a
            for (int i = 1; i <= n; i++) {
                nums[i] = in.nextInt();
            }
            //mapB,存数组b中 元素 + 频数
            HashMap<Integer, Integer> mapB = new HashMap<>();
            //map，存 滑动窗口 元素 + 频数
            HashMap<Integer, Integer> map = new HashMap<>();
            //初始化mapB
            for (int i = 1; i <= m; i++) {
                int tmp = in.nextInt();
                mapB.put(tmp, mapB.getOrDefault(tmp, 0) + 1);
            }
            //初始化首轮map
            for (int i = 1; i <= m; i++) {
                map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
            }
            //初始化首轮res
            for (Integer key : mapB.keySet()) {
                res += Math.min(mapB.get(key), map.getOrDefault(key, 0));
            }
            if (res >= k) {
                ans ++;
            }
            //for循环l,r 控制开滑
            for (int l = 1, r = m + 1 ; r <= n; l++, r++) {
                //移出左边
                if (mapB.containsKey(nums[l]) && mapB.get(nums[l]) >= map.get(nums[l])) {
                    res --;
                }
                map.put(nums[l], map.get(nums[l]) - 1);
                if (map.get(nums[l]) == 0) {
                    map.remove(nums[l]);
                }
                //添加右边
                if (mapB.containsKey(nums[r]) &&
                        mapB.get(nums[r]) > map.getOrDefault(nums[r], 0)) {
                    res ++;
                }
                map.put(nums[r], map.getOrDefault(nums[r], 0) + 1);
                if (res >= k) {
                    ans ++;
                }
            }
            out.println(ans);
        }
        out.flush();
    }
}