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

题目链接

题目描述

给定一个长度为 $n$ 的整数数组 $A$ 和一个长度为 $m$ 的整数数组 $B$ 。一个长度为 $m$ 的数组如果可以通过重新排列元素，与数组 $B$ 在对应位置上至少有 $k$ 个元素相等，则称该数组是“可匹配的”。

任务是，计算数组 $A$ 中有多少个长度为 $m$ 的连续子段是“可匹配的”。

解题思路

这个问题的核心是判断一个子段和一个目标数组 $B$ 在元素构成上的相似度。一个子段“可匹配”，意味着该子段与数组 $B$ 的元素交集大小至少为 $k$ 。具体来说，对于每一种数值 $v$ ，它在交集中的贡献是 $\min(\text{子段中 } v \text{ 的数量}, \text{B 中 } v \text{ 的数量})$ 。所有数值贡献的总和就是匹配度。

由于我们需要对 $A$ 的所有长度为 $m$ 的连续子段进行判断，这自然引出了滑动窗口的解法。我们可以维护一个长度为 $m$ 的窗口，在 $A$ 上从左到右滑动，并高效地更新窗口内的元素频率以及与 $B$ 的匹配度。

算法步骤如下：

预计算：首先，使用哈希表（ $map$ ）计算出数组 $B$ 中每个元素的频率，记为 $freq\_B$ 。
初始化窗口：
- 创建一个哈希表 $freq\_window$ 来维护当前窗口内元素的频率。
- 处理 $A$ 的前 $m$ 个元素，填充 $freq\_window$ 。
- 计算初始窗口的匹配度 $match\_count$ 。这个值等于 $\sum_{v} \min(freq\_window[v], freq\_B[v])$ 。
- 如果 $match\_count \ge k$ ，则答案计数器加一。
滑动窗口：
- 从第 $m$ 个元素开始，向右滑动窗口直到数组末尾。在每次滑动中：
- 移除左边界元素：设要移除的元素为 $left\_val$ 。在更新 $freq\_window$ 之前，检查它是否对匹配度有贡献。如果 $freq\_window[left\_val] \le freq\_B[left\_val]$ ，说明移除的这个元素是一个有效的匹配元素，因此将 $match\_count$ 减一。然后，更新 $freq\_window[left\_val]$ 。
- 添加右边界元素：设新加入的元素为 $right\_val$ 。先更新 $freq\_window[right\_val]$ 。更新后，检查它是否能形成新的匹配。如果 $freq\_window[right\_val] \le freq\_B[right\_val]$ ，说明新加入的元素是一个有效的匹配元素，因此将 $match\_count$ 加一。
- 检查并更新答案：在每次滑动后，检查当前的 $match\_count$ 是否不小于 $k$ 。如果是，则答案计数器加一。
多组测试：题目要求处理多组测试用例，因此需要将上述逻辑封装起来，循环调用。

通过这种方式，每次窗口滑动时，我们都只对进出窗口的两个元素进行 $O(1)$ 的更新（哈希表操作均摊为 $O(1)$ ），从而将每个测试用例的总时间复杂度优化到 $O(n)$ 。

代码

c++
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> freq_b;
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < m; ++i) {
        int val;
        cin >> val;
        freq_b[val]++;
    }

    map<int, int> freq_window;
    int match_count = 0;
    int ans = 0;

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

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

    // 滑动窗口
    for (int i = m; i < n; ++i) {
        // 移除左边界元素
        int left_val = a[i - m];
        if (freq_window[left_val] <= freq_b[left_val]) {
            match_count--;
        }
        freq_window[left_val]--;

        // 添加右边界元素
        int right_val = a[i];
        if (freq_window[right_val] < freq_b[right_val]) {
            match_count++;
        }
        freq_window[right_val]++;

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

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

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

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

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

        Map<Integer, Integer> freqWindow = new HashMap<>();
        int matchCount = 0;
        int ans = 0;

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

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

        // 滑动窗口
        for (int i = m; i < n; i++) {
            // 移除左边界元素
            int leftVal = a[i - m];
            int currentFreqLeft = freqWindow.get(leftVal);
            int targetFreqLeft = freqB.getOrDefault(leftVal, 0);
            if (currentFreqLeft <= targetFreqLeft) {
                matchCount--;
            }
            freqWindow.put(leftVal, currentFreqLeft - 1);

            // 添加右边界元素
            int rightVal = a[i];
            int currentFreqRight = freqWindow.getOrDefault(rightVal, 0);
            int targetFreqRight = freqB.getOrDefault(rightVal, 0);
            if (currentFreqRight < targetFreqRight) {
                matchCount++;
            }
            freqWindow.put(rightVal, currentFreqRight + 1);

            if (matchCount >= k) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

import sys
from collections import defaultdict

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

    freq_b = defaultdict(int)
    for val in b:
        freq_b[val] += 1

    freq_window = defaultdict(int)
    match_count = 0
    ans = 0

    # 初始化第一个窗口
    for i in range(m):
        if freq_window[a[i]] < freq_b[a[i]]:
            match_count += 1
        freq_window[a[i]] += 1
    
    if match_count >= k:
        ans += 1

    # 滑动窗口
    for i in range(m, n):
        # 移除左边界元素
        left_val = a[i - m]
        if freq_window[left_val] <= freq_b[left_val]:
            match_count -= 1
        freq_window[left_val] -= 1

        # 添加右边界元素
        right_val = a[i]
        if freq_window[right_val] < freq_b[right_val]:
            match_count += 1
        freq_window[right_val] += 1
        
        if match_count >= k:
            ans += 1
            
    print(ans)

def main():
    t = int(sys.stdin.readline())
    for _ in range(t):
        solve()

if __name__ == "__main__":
    main()

算法及复杂度

算法：滑动窗口 + 哈希表。
时间复杂度： $O(\sum n)$ ，对于每个测试用例，时间复杂度为 $O(n)$ ，因为我们只对数组 $A$ 进行了一次线性扫描。 $\sum n$ 是所有测试用例的 $n$ 的总和。
空间复杂度： $O(\sum m)$ ，主要用于存储数组 $B$ 和窗口的频率哈希表。