首页 > 试题广场 >

可匹配子段计数

[编程题]可匹配子段计数

热度指数：1554 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 给定整数数组 $a$ （长度 $n$ ）与数组 $b$ （长度 $m$ ， $m\leqq n$ ）。设一个长度为 $m$ 的数组 $c$ 被称为 可匹配的，当且仅当将 $c$ 的元素重新排列后，与数组 $b$ 在对应位置上至少有 $k$ 个元素相等。
$\hspace{15pt}$ 对于 $a$ 中的每一个长度恰为 $m$ 的连续子段，都可视为一个候选数组 $c$ 。求满足条件的子段数量。

【形式化解释】
$\hspace{15pt}$ 若子段 $a_{l..l+m-1}$ 经重排可与 $b$ 至少 $k$ 个位置相等，则称该子段为"可匹配的"。等价地，设 $cnt_x(S)$ 为元素 $x$ 在序列 $S$ 中出现次数，则子段 $c$ 的"匹配度"为 $\operatorname{match}(c)=\sum_{x} \min\bigl(cnt_x(c),\ cnt_x(b)\bigr)$ ，若 $\operatorname{match}(c)\geqq k$ 则符合要求。

输入描述:

第一行输入整数 ——测试用例组数。 
每个测试用例： 
一行三个整数 ； 
一行  个整数 ； 
一行  个整数 。 
输入保证所有测试用例的  之和、 之和均不超过 。

输出描述:

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

示例1

输入

输出

算法知识视频讲解

Python3

HIKong

import sys
from collections import Counter

# 在 a 里滑动一个长度为 m 的窗口，
# 每次问：这个窗口里的数字，
# 和 b 最多能对上几个？
# 如果 ≥ k，就算一个好窗口。最终输出好窗口的数量。天天把题目写那么绕干蛤啊，嗯→膜⬆！
# 滑动窗口可以简单的理解成，右边进来一个数，然后左边出去一个
t = int(input())
for _ in range(t):
    n, m, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))

    need = Counter(b)
    window = Counter()
    match = 0 # 连续字段中数字匹配的次数
    ans = 0

    # 双指针
    left = 0
    for right in range(n):
        x = a[right]
        window[x] += 1
        if window[x] <= need[x]:
            match += 1

        # 保持窗口长度为 m。出去一个，自然匹配次数要-1
        if right - left + 1 > m:
            y = a[left]
            if window[y] <= need[y]:
                match -= 1
            window[y] -= 1
            left += 1

        if right - left + 1 == m and match >= k:
            ans += 1
    print(ans)

发表于 2025-12-20 20:25:44 回复(0)

JavaScript Node

xuwzen

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
    const t = Number(await readline());

    for (let l = 0; l < t; l++) {
        const [n, m, k] = (await readline()).split(" ").map(Number);
        const listA = (await readline()).split(" ").map(Number);
        const listB = (await readline()).split(" ").map(Number);

        let map = new Map();
        for (let c of listB) {
            map.set(c, (map.get(c) || 0) + 1);
        }

        let i = 0;
        let j = 0;
        let cnt = 0;
        let countMap = new Map();
        while (j < m) {
            countMap.set(listA[j], (countMap.get(listA[j]) || 0) + 1);
            if (
                map.has(listA[j]) &&
                countMap.get(listA[j]) <= map.get(listA[j]) &&
                j < m
            ) {
                cnt++;
            }
            j++;
        }
        j--;

        let ans = 0;
        if (cnt >= k) {
            ans++;
            // console.log('0  ans', ans);
        }
        // console.log('initial i, j ', i, j);

        while (j < n) {
            i++;
            j++;
            const removedChar = listA[i - 1];
            countMap.set(removedChar, countMap.get(removedChar) - 1);
            if (
                map.has(removedChar) &&
                countMap.get(removedChar) + 1 <= map.get(removedChar)
            ) {
                cnt--;
            }
            const addedChar = listA[j];
            countMap.set(addedChar, (countMap.get(addedChar) || 0) + 1);
            if (
                map.has(addedChar) &&
                countMap.get(addedChar) - 1 < map.get(addedChar)
            ) {
                cnt++;
            }
            // console.log("i,j", i, j, new Map(countMap));
            if (cnt >= k && j < n) {
                ans++;
                // console.log("cnt, ans", cnt, ans);
                // console.log("i,j ", i, j);
            }
        }
        console.log(ans);
    }
})();

发表于 2025-09-29 17:30:33 回复(0)

Java

牛客916838684号

怎么简单题都这么难？懒得删除注释了

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int l = in.nextInt();
        for (int i = 0; i < l; i++) {
            int n = in.nextInt();
            int m = in.nextInt();
            int k = in.nextInt();

            int[] nn = new int[n];

            for (int j = 0; j < n; j++) {
                nn[j] = in.nextInt();
                // System.out.print(nn[i]);
                // System.out.println();
            }

            int[] mm = new int[m];

            for (int q = 0; q < m; q++) {
                mm[q] = in.nextInt();
                //                 System.out.print(mm[i]);
                // System.out.println();
            }

            int count = 0;
            int tot = 0;

            for (int w = 0; w < n - m+1; w++) {
                int[] ww = new int[m];
                for (int e = 0; e < m; e++) {
                    ww[e] = nn[e + w];
                    // System.out.println(ww[e]);
                }

                // for (int e=0; e<m; e++){
                    // System.out.print("子串内容为"+ww[e]);
                    // System.out.println();
                // }
                for (int e = 0; e < m; e++) {
                    if (ww[e] == mm[e]) {
                        count++;
                        // System.out.println("相等了几个？"+count);
                    }
                }
                if (count >= k) {
                    // System.out.println("已匹配，计数归零");
                    tot++;
                    count = 0;
                }
            }
            System.out.println(tot);

        }

    }
}

发表于 2025-09-29 11:04:24 回复(0)

Python3

mock1

这道题不应该是简单题的，写起来很复杂

发表于 2025-09-26 10:55:08 回复(0)

草海桐

下面代码有什么问题吗？有一个测试用例过不了（测试用例数为9的那个）。

package main

import (
	"fmt"
)

func Min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	var n, m, k, num int
    fmt.Scanf("%d", &num)
    for num != 0 {
        fmt.Scanf("%d %d %d", &n, &m, &k)
        var a = make([]int, n)
        var b = make([]int, m)
        var aMap = make(map[int]int, m) // 维护 a 搜索串中各个字符的频数
        var bMap = make(map[int]int, m) // 维护 b 中各个字符的频数
        for i := 0; i < n; i++ {
            fmt.Scanf("%d", &a[i])
        }
        for i := 0; i < m; i++ {
            fmt.Scanf("%d", &b[i])
            bMap[b[i]]++
        }

        var result int =0 
        // 先判断a[0:m-1]与b的匹配度
        var p int = 0
        for i := 0; i < m; i++ {
            aMap[a[i]]++
        }
        for i := 0; i < m; i++ {
            p += Min(aMap[i], bMap[i])
        }
        if p >= k {
            result++
        }
        for i, j := 1, m; j < n; i,j = i+1,j+1 { // 窗口每次整体左移一个
            if aMap[a[i-1]] <= bMap[a[i-1]] && aMap[a[i-1]] > 0{ // 左部减少的元素a[i-1]
                p--
            }
            aMap[a[i-1]]-- 

            if aMap[a[j]] < bMap[a[j]] && bMap[a[j]] >0 { // 右部增加的元素a[j]
                p++
            }
            aMap[a[j]]++

            if p >= k {
                result++
            }
        }
        fmt.Println(result)
        num--
    }
}

发表于 2025-08-30 22:18:21 回复(0)

Java

六路折梅手

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
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());
        while (t-- > 0) {
            per(br);
        }

    }
    public static void per(BufferedReader br)  throws IOException {
        String[] line1 = br.readLine().split(" ");
        int n = Integer.parseInt(line1[0]);
        int m = Integer.parseInt(line1[1]);
        int k = Integer.parseInt(line1[2]);
        int[] arrA = Arrays.stream(br.readLine().split(" ")).mapToInt(
                         Integer::parseInt).toArray();
        int[] arrB = Arrays.stream(br.readLine().split(" ")).mapToInt(
                         Integer::parseInt).toArray();

        Map<Integer, Integer> mapM = new HashMap<>(); //A上的长为m的滑动窗口
        Map<Integer, Integer> mapB = new HashMap<>(); //B的变量统计
        int curMatch = 0; //匹配的元素数目
        int res = 0; //满足条件的子串数

        //1.统计B数组的元素数目
        for (int i = 0; i < arrB.length; i++) {
            mapB.put(arrB[i], mapB.getOrDefault(arrB[i], 0) + 1);
        }
        //初始化第一个窗口
        for (int i = 0; i < m; i++) {
            mapM.put(arrA[i], mapM.getOrDefault(arrA[i], 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : mapB.entrySet()) {
            int conutB = entry.getValue();
            curMatch += Math.min(mapM.getOrDefault(entry.getKey(), 0), conutB);
        }
        if (curMatch >= k) {
            res++;
        }
        //2.滑动窗口在A数组中滑动
        //统计滑动窗口中所有元素是否在B中
        for (int l = 0, r = m; r < arrA.length; l++, r++) {
            //移除左侧元素
            if (mapB.containsKey(arrA[l]) && mapM.getOrDefault(arrA[l],
                    0) <= mapB.get(arrA[l])) {
                curMatch-- ;
            }
            mapM.put(arrA[l], mapM.getOrDefault(arrA[l],0) - 1); //计数减一
            if (mapM.get(arrA[l]) == 0) {
                mapM.remove(arrA[l]);
            }

            //添加右侧元素
            if (mapB.containsKey(arrA[r]) &&
                    mapM.getOrDefault(arrA[r], 0) < mapB.get(arrA[r])) {
                curMatch++;
            }
            mapM.put(arrA[r], mapM.getOrDefault(arrA[r], 0) + 1);
            if (curMatch >= k) {
                res++;
            }
        }
        System.out.println(res);
    }
}

发表于 2025-08-26 23:37:13 回复(0)

赵成1212

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    int t;
    cin >> t;
    vector<int> res(t);

    for (int i = 0; i < t; ++i) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<int> a;
        vector<int> b;
        unordered_map<int , int> ma;
        unordered_map<int, int> mb;
        for (int i = 0; i < n; ++i) {
            int x;
            cin >> x;
            a.push_back(x);
        }
        for (int i = 0; i < m; ++i) {
            int x; 
            cin >> x;
            b.push_back(x);
            mb[x]++;
        }

        int cnt = 0;
        // init
        for (int i = 0; i < m; ++i) {
            ma[a[i]]++;
        }
        int match_cnt = 0;
        for (auto& [x, count] : mb) {
            if (ma.find(x) != ma.end()) {
                match_cnt += min(count, ma[x]);
            }
        }
        if (match_cnt >= k) cnt++;
        for (int i = m; i < n; ++i) {
            int left_val = a[i - m];
            if (mb.find(left_val) != mb.end() && ma[left_val] <= mb[left_val]) {
                match_cnt--;
            }
            ma[left_val]--;
            if (ma[left_val] == 0) ma.erase(left_val);
            int right_val = a[i];
            ma[right_val]++;
            if (mb.find(right_val) != mb.end() && ma[right_val] <= mb[right_val]) {
                match_cnt++;
            }
            if (match_cnt >= k) cnt++;
        }
        res[i] = cnt;
    }
    for (int i = 0; i < t; ++i) {
        cout << res[i] << endl;
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

发表于 2025-08-14 17:07:22 回复(0)

提交观点

问题信息

双指针

难度：

7条回答 23收藏 531浏览

可匹配子段计数

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题