首页 > 试题广场 >

可匹配子段计数

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

热度指数：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

输入

输出

算法知识视频讲解

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)

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)

提交观点

问题信息

双指针

难度：

2条回答 23收藏 533浏览

可匹配子段计数

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

相关试题