华为OD机试真题——最小矩阵宽度（宽度最小的子矩阵）（2025A卷：200分）Java/python/JavaScript/C/C++/GO最佳实现

2025 A卷 200分 题型

本专栏内全部题目均提供Java、python、JavaScript、C、C++、GO六种语言的最佳实现方式；

并且每种语言均涵盖详细的问题分析、解题思路、代码实现、代码详解、3个测试用例以及综合分析；

本文收录于专栏：《2025华为OD真题目录+全流程解析+备考攻略+经验分享》

华为OD机试真题《最小矩阵宽度（宽度最小的子矩阵）》：

---

文章快捷目录

题目描述及说明

Java

python

JavaScript

C

GO

---

题目名称：最小矩阵宽度（宽度最小的子矩阵）

---

• 知识点：滑动窗口、哈希表（计数覆盖）
• 时间限制：1秒
• 空间限制：256MB
• 限定语言：不限

---

题目描述

给定一个矩阵，包含 N * M 个整数，和一个包含 K 个整数的数组。现在要求在这个矩阵中找一个宽度最小的子矩阵，要求子矩阵包含数组中所有的整数（包括重复数字）。

输入描述：

1. 第一行输入两个正整数 N, M，表示矩阵大小。
2. 接下来 N 行，每行 M 个整数，表示矩阵内容。
3. 下一行包含一个正整数 K。
4. 下一行包含 K 个整数，表示需要包含的数组，可能存在重复数字。
   所有输入数据小于 1000。

输出描述：
输出一个整数，表示满足要求的子矩阵的最小宽度（连续列数）。若找不到，输出 -1。

示例 1：
输入：

2 5  
1 2 2 3 1  
2 3 2 3 2  
3  
1 2 3  

输出：

2  

说明：矩阵第0、3列包含 1, 2, 3，第3、4列也包含 1, 2, 3，最小宽度为2。

示例 2：
输入：

2 5  
1 2 2 3 1  
1 3 2 3 4  
3  
1 1 4  

输出：

5  

说明：只有所有列才能覆盖 1, 1, 4，宽度为5。

---

Java

问题分析

我们需要在矩阵中找到包含所有目标元素的最窄连续列区间。子矩阵必须包含目标数组中的所有元素，包括重复元素，并且宽度（列数）最小。

解题思路

1. 预处理目标数组：统计每个元素的出现次数。
2. 预处理矩阵列：统计每列中元素的出现次数。
3. 遍历所有可能的窗口宽度：从1到M，检查每个宽度的所有连续列区间是否满足目标频率要求，找到最小的宽度。

代码实现

import java.util.*;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int N = scanner.nextInt();int M = scanner.nextInt();int[][] matrix = new int[N][M];// 读取矩阵for (int i = 0; i < N; i++) {for (int j = 0; j < M; j++) {matrix[i][j] = scanner.nextInt();}}// 读取目标数组int K = scanner.nextInt();int[] target = new int[K];for (int i = 0; i < K; i++) {target[i] = scanner.nextInt();}// 预处理：统计目标数组中每个元素出现的次数Map<Integer, Integer> targetFreq = new HashMap<>();for (int num : target) {targetFreq.put(num, targetFreq.getOrDefault(num, 0) + 1);}// 预处理：统计每列的元素频率List<Map<Integer, Integer>> columns = new ArrayList<>();for (int col = 0; col < M; col++) {Map<Integer, Integer> freq = new HashMap<>();for (int row = 0; row < N; row++) {int num = matrix[row][col];freq.put(num, freq.getOrDefault(num, 0) + 1);}columns.add(freq);}// 遍历所有可能的窗口宽度for (int width = 1; width <= M; width++) {for (int start = 0; start <= M - width; start++) {Map<Integer, Integer> sum = new HashMap<>();// 累加当前窗口内的所有列for (int col = start; col < start + width; col++) {Map<Integer, Integer> colFreq = columns.get(col);for (Map.Entry<Integer, Integer> entry : colFreq.entrySet()) {int num = entry.getKey();sum.put(num, sum.getOrDefault(num, 0) + entry.getValue());}}// 检查是否满足目标频率boolean valid = true;for (Map.Entry<Integer, Integer> entry : targetFreq.entrySet()) {if (sum.getOrDefault(entry.getKey(), 0) < entry.getValue()) {valid = false;break;}}if (valid) {System.out.println(width);return;}}}System.out.println(-1);}
}

代码详细解析

1. 读取输入：读取矩阵大小、矩阵内容、目标数组。
2. 统计目标频率：使用HashMap记录目标数组中每个元素的出现次数。
3. 预处理列频率：对每一列统计各元素的出现次数，存储在columns列表中。
4. 遍历窗口宽度：从1到M，检查每个可能的连续列区间。
5. 累加列频率：对当前窗口内的所有列，累加各元素的出现次数到sum。
6. 验证频率：检查累加后的频率是否满足目标要求，若满足则立即输出当前宽度。

示例测试

示例1：
输入：

2 5
1 2 2 3 1
2 3 2 3 2
3
1 2 3

输出：

2

示例2：
输入：

2 5
1 2 2 3 1
1 3 2 3 4
3
1 1 4

输出：

5

综合分析

• 时间复杂度：O(M² * K)，M为矩阵列数，K为每列平均元素数。在题目限制下可行。
• 空间复杂度：O(M * K)，存储每列的元素频率。
• 正确性：遍历所有可能的窗口，确保找到最小宽度。
• 适用性：简单直观，适用于输入规模较小的情况。

---

python

问题分析

我们需要在矩阵中找到包含所有目标元素的最窄连续列区间。子矩阵必须包含目标数组中的所有元素，包括重复次数，并且宽度（列数）最小。

---

解题思路

1. 预处理目标数组：统计每个元素的出现次数。
2. 预处理矩阵列：统计每列中元素的出现次数。
3. 遍历所有可能的窗口宽度：从1到M，检查每个宽度的所有连续列区间是否满足目标频率要求，找到最小的宽度。

---

代码实现

from collections import defaultdictdef main():# 读取输入n, m = map(int, input().split())matrix = []for _ in range(n