题解 | #可匹配子段计数#

题目链接

题目描述

给定一个长度为 $n$ 的整数数组 $A$ 和一个长度为 $m$ 的整数数组 $B$ （ $m \le n$ ），以及一个整数 $k$ 。一个长度为 $m$ 的数组被称为可匹配的，当且仅当该数组的元素重排后，能与数组 $B$ 在对应位置上至少有 $k$ 个元素相等。

我们需要对数组 $A$ 中所有长度为 $m$ 的连续子段进行判断，统计其中有多少个是“可匹配的”。

形式化地，对于 $A$ 的一个子段，我们计算它的“匹配度”。匹配度定义为：对于所有在 $B$ 中出现过的整数 $v$ ，取其在子段中出现次数和在 $B$ 中出现次数的最小值，然后将这些最小值求和。如果一个子段的匹配度大于等于 $k$ ，则该子段是可匹配的。

输入:

第一行一个整数 $T$ ，表示测试用例组数。
每个测试用例：
- 第一行三个整数 $n, m, k$ 。
- 第二行 $n$ 个整数，表示数组 $A$ 。
- 第三行 $m$ 个整数，表示数组 $B$ 。

输出:

对每个测试用例，输出一个整数，表示满足条件的子段数量。

解题思路

本题的核心是高效地计算每个长度为 $m$ 的子段与数组 $B$ 的匹配度。一个朴素的方法是遍历每个子段并用哈希表计算匹配度，但时间复杂度会达到 $\mathcal{O}(n \cdot m)$ ，无法通过所有测试用例。

更优的方法是使用滑动窗口结合哈希表（频率映射）。

预处理：首先，我们用一个哈希表 mapB 统计数组 $B$ 中每个元素的出现次数。这个表在单个测试用例中是固定不变的。
初始化窗口：
- 我们维护一个大小为 $m$ 的滑动窗口，并用另一个哈希表 mapA 统计当前窗口内各元素的出现次数。
- 我们计算第一个窗口（即 $A[0 \dots m-1]$ ）的初始匹配度 current_match。遍历 mapB 中的每个键值对 (v, countB)，v 对匹配度的贡献是 $\min(\text{mapA.get}(v), \text{countB})$ 。将所有贡献累加得到 current_match。
- 如果 current_match >= k，则答案计数器 ans 加 1。
滑动窗口：
- 我们将窗口向右滑动一格，从 $i = m$ 遍历到 $n-1$ 。每次滑动，一个元素 remove_val = A[i-m] 离开窗口，一个元素 add_val = A[i] 进入窗口。
- 我们不需要重新计算整个窗口的匹配度，而是高效地更新 current_match：
  - 元素离开 (remove_val)：
    - 如果 remove_val 在 mapB 中存在，并且它在离开前窗口中的数量 mapA.get(remove_val) 不超过 mapB.get(remove_val)，说明这次移除使得一个有效的匹配减少了，因此 current_match 需要减 1。
    - 更新 mapA 中 remove_val 的计数。
  - 元素进入 (add_val)：
    - 如果 add_val 在 mapB 中存在，并且它在进入前窗口中的数量 mapA.get(add_val) 小于 mapB.get(add_val)，说明这次加入产生了一个新的有效匹配，因此 current_match 需要加 1。
    - 更新 mapA 中 add_val 的计数。
- 每次滑动后，检查 current_match >= k 是否成立，如果成立则 ans 加 1。
输出结果：遍历完所有窗口后，输出 ans。

这种方法使得每次窗口滑动的更新操作仅需常数或对数时间（取决于哈希表的实现），总时间复杂度大大降低。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <map>

using namespace std;

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    map<int, int> mapB;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        int val;
        cin >> val;
        mapB[val]++;
    }

    map<int, int> mapA;
    int current_match = 0;
    int ans = 0;

    // 初始化第一个窗口
    for (int i = 0; i < m; ++i) {
        mapA[a[i]]++;
    }

    for (auto const& [val, countB] : mapB) {
        if (mapA.count(val)) {
            current_match += min(mapA[val], countB);
        }
    }

    if (current_match >= k) {
        ans++;
    }

    // 滑动窗口
    for (int i = m; i < n; ++i) {
        int remove_val = a[i - m];
        int add_val = a[i];

        // 处理移出窗口的元素
        if (mapB.count(remove_val)) {
            if (mapA[remove_val] <= mapB[remove_val]) {
                current_match--;
            }
        }
        mapA[remove_val]--;
        if (mapA[remove_val] == 0) {
            mapA.erase(remove_val);
        }

        // 处理加入窗口的元素
        if (mapB.count(add_val)) {
            if (mapA.count(add_val) < 1 || mapA[add_val] < mapB[add_val]) {
                current_match++;
            }
        }
        mapA[add_val]++;

        if (current_match >= k) {
            ans++;
        }
    }
    cout << ans << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            solve(sc);
        }
    }

    public static void solve(Scanner sc) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        Map<Integer, Integer> mapB = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int val = sc.nextInt();
            mapB.put(val, mapB.getOrDefault(val, 0) + 1);
        }

        Map<Integer, Integer> mapA = new HashMap<>();
        int currentMatch = 0;
        int ans = 0;

        // 初始化第一个窗口
        for (int i = 0; i < m; i++) {
            mapA.put(a[i], mapA.getOrDefault(a[i], 0) + 1);
        }

        for (Map.Entry<Integer, Integer> entry : mapB.entrySet()) {
            int val = entry.getKey();
            int countB = entry.getValue();
            currentMatch += Math.min(mapA.getOrDefault(val, 0), countB);
        }

        if (currentMatch >= k) {
            ans++;
        }

        // 滑动窗口
        for (int i = m; i < n; i++) {
            int removeVal = a[i - m];
            int addVal = a[i];

            // 处理移出窗口的元素
            if (mapB.containsKey(removeVal)) {
                if (mapA.getOrDefault(removeVal, 0) <= mapB.get(removeVal)) {
                    currentMatch--;
                }
            }
            mapA.put(removeVal, mapA.get(removeVal) - 1);
            if (mapA.get(removeVal) == 0) {
                mapA.remove(removeVal);
            }

            // 处理加入窗口的元素
            if (mapB.containsKey(addVal)) {
                if (mapA.getOrDefault(addVal, 0) < mapB.get(addVal)) {
                    currentMatch++;
                }
            }
            mapA.put(addVal, mapA.getOrDefault(addVal, 0) + 1);
            
            if (currentMatch >= k) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

from collections import Counter

def solve():
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    map_b = Counter(b)
    map_a = Counter(a[:m])
    
    current_match = 0
    # 计算初始匹配度
    for val, count_b in map_b.items():
        current_match += min(map_a.get(val, 0), count_b)

    ans = 0
    if current_match >= k:
        ans += 1

    # 滑动窗口
    for i in range(m, n):
        remove_val = a[i - m]
        add_val = a[i]
        
        # 处理移出窗口的元素
        if remove_val in map_b:
            if map_a.get(remove_val, 0) <= map_b.get(remove_val, 0):
                current_match -= 1
        map_a[remove_val] -= 1
        if map_a[remove_val] == 0:
            del map_a[remove_val]
            
        # 处理加入窗口的元素
        if add_val in map_b:
            if map_a.get(add_val, 0) < map_b.get(add_val, 0):
                current_match += 1
        map_a[add_val] = map_a.get(add_val, 0) + 1

        if current_match >= k:
            ans += 1
            
    print(ans)


t = int(input())
for _ in range(t):
    solve()

算法及复杂度

算法：滑动窗口 + 哈希表
时间复杂度：对于每个测试用例，预处理数组 $B$ 需要 $\mathcal{O}(m)$ 。初始化第一个窗口需要 $\mathcal{O}(m)$ ，计算初始匹配度需要 $\mathcal{O}(\min(m, |\Sigma|))$ ，其中 $|\Sigma|$ 是值域大小。滑动过程共 $n-m$ 步，每步更新哈希表和匹配度是 $\mathcal{O}(\log m)$ （对于 std::map）或 $\mathcal{O}(1)$ （平均，对于 HashMap/dict）。因此总时间复杂度为 $\mathcal{O}(n \log m)$ 或 $\mathcal{O}(n)$ 。考虑到所有测试用例的 $N$ 和 $M$ 总和限制，该复杂度是高效的。
空间复杂度： $\mathcal{O}(n+m)$ ，用于存储输入的数组 $A$ 和 $B$ ，以及两个哈希表。哈希表的大小最多为 $m$ 。