给定一个矩阵，包含N*M个整数，和一个包含K个整数的数组现在要求在这个矩阵中找一个宽度最小的子矩阵，要求子矩阵包含数组中所有的整数。
第一行输入两个正整数N，M，表示矩阵大小。
接下来N行M列表示矩阵内容。下一行包含一个正整数K。下一行包含K个整数，表示所需包含的数组，K个整数可能存在重复数字。
所有输入数据小于1000。
输出包含一个整数，表示满足要求子矩阵的最小宽度，若找不到，输出-1
2 5
1 2 2 3 1
2 3 2 3 2
3
1 2 3
2
本题只需要找到最小宽度的子矩阵，对高度不做要求。
举个例子，对于题目所给示例
1 2 2 3 1
2 3 2 3 2
选择子矩阵
1 2 2
和
1 2 2
2 3 2
在只考虑宽度的限定条件下，它们的宽度均为3。
贪心地思考这个问题，我们在每次选择时必然会把列向的整个高度都选择上，这样找到的子矩阵的宽度才能够尽可能地小。
因此问题就转变为了，在行向选择若干连续的列，使得构成的子矩阵能够覆盖给定的长度为K的数组。这显然就是一个借助哈希表来辅助的滑窗问题。
我们可以先把每一列**“拍扁”**，用一个二维列表col_contain_lst统计每一列所包含的元素。
col_contain_lst[i]是一个计数器哈希表，记录了第i列所包含的元素以及个数。
其构建过程如下
col_contains_lst = [Counter() for _ in range(m)]
for j in range(m):
for i in range(n):
val = mat[i][j]
col_contains_lst[j][val] += 1
构建一个新的哈希表win_cnt，用于储存窗口中的元素以及其个数。此外还需要另一个哈希表cnt，用于储存长度为K的目标数组的元素以及个数。
考虑滑窗三问三答。
Q1：对于每一个右指针right所指的列col，做什么操作？
Q2：什么时候要令左指针left右移？left对应的列col_left做什么操作？while中的循环不变量是什么？
Q3：什么时候进行ans的更新？
A1：将第right列各个元素出现的个数，加入到用于储存窗口中的元素以及其个数的哈希表win_cnt中
A2：哈希表cnt的每一个元素均在win_cnt中出现，且个数小于等于窗口中的元素个数。可以新建一个check()函数来表示这个过程。
def check(cnt, win_cnt):
return all(cnt[k] <= win_cnt[k] for k in cnt.keys())
left不断右移，直到该条件不满足。
A3：当check()满足时，可以更新答案。
# 题目：【不定滑窗】2023C-最小矩阵宽度
# 分值：200
# 作者：许老师-闭着眼睛学数理化
# 算法：不定滑窗
# 代码看不懂的地方，请直接在群上提问
from collections import Counter
from math import inf
# 用于判断窗口中元素个数是否均大于等于给定数组元素个数的函数
def check(cnt, win_cnt):
return all(cnt[k] <= win_cnt[k] for k in cnt.keys())
# 输入矩阵大小n、m
n, m = map(int, input().split())
mat = list()
# 输入n行
for _ in range(n):
mat.append(list(map(int, input().split())))
# 输入数组的长度k
k = int(input())
# 输入目标覆盖数组
nums = list(map(int, input().split()))
# 构建一个长度为m的列表col_contains_lst
# 其中内层元素为一个哈希表计数器
# col_contains_lst[i]记录了mat第i列所包含的元素以及个数
col_contains_lst = [Counter() for _ in range(m)]
# 遍历每一列
for j in range(m):
# 考虑第j列的每一行
for i in range(n):
# mat[i][j]的元素是val
val = mat[i][j]
# 在第j列的位置中，val出现的次数+1
col_contains_lst[j][val] += 1
# 构建目标数组的哈希表，统计其中元素以及个数
cnt = Counter(nums)
# 构建滑窗哈希表，统计窗口中的元素以及个数
win_cnt = Counter()
# 初始化答案，由于要算最小宽度，所以初始化为一个较大的值
# 此处取无限大或者m+1均可
ans = inf
# 初始化窗口左指针
left = 0
# 进行滑窗过程，一共需要遍历m列
for right in range(m):
# A1
for k, v in col_contains_lst[right].items():
win_cnt[k] += v
while check(cnt, win_cnt):
# A3
ans = min(ans, right-left+1)
# A2
for k, v in col_contains_lst[left].items():
win_cnt[k] -= v
left += 1
print(ans if ans != inf else -1)
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[][] mat = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
mat[i][j] = scanner.nextInt();
}
}
int k = scanner.nextInt();
int[] nums = new int[k];
for (int i = 0; i < k; i++) {
nums[i] = scanner.nextInt();
}
List<Map<Integer, Integer>> colContainsList = new ArrayList<>();
for (int i = 0; i < m; i++) {
colContainsList.add(new HashMap<>());
}
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
int val = mat[i][j];
colContainsList.get(j).put(val, colContainsList.get(j).getOrDefault(val, 0) + 1);
}
}
Map<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
Map<Integer, Integer> windowCountMap = new HashMap<>();
int answer = Integer.MAX_VALUE;
int left = 0;
for (int right = 0; right < m; right++) {
for (Map.Entry<Integer, Integer> entry : colContainsList.get(right).entrySet()) {
int key = entry.getKey();
int value = entry.getValue();
windowCountMap.put(key, windowCountMap.getOrDefault(key, 0) + value);
}
while (check(countMap, windowCountMap)) {
answer = Math.min(answer, right - left + 1);
for (Map.Entry<Integer, Integer> entry : colContainsList.get(left).entrySet()) {
int key = entry.getKey();
int value = entry.getValue();
windowCountMap.put(key, windowCountMap.get(key) - value);
}
left++;
}
}
System.out.println(answer != Integer.MAX_VALUE ? answer : -1);
}
public static boolean check(Map<Integer, Integer> countMap, Map<Integer, Integer> windowCountMap) {
for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
int key = entry.getKey();
int value = entry.getValue();
if (windowCountMap.getOrDefault(key, 0) < value) {
return false;
}
}
return true;
}
}
#include <iostream>
#include <vector>
#include <unordered_map>
#include <climits>
using namespace std;
bool check(unordered_map<int, int>& countMap, unordered_map<int, int>& windowCountMap) {
for (auto& entry : countMap) {
int key = entry.first;
int value = entry.second;
if (windowCountMap[key] < value) {
return false;
}
}
return true;
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> mat(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> mat[i][j];
}
}
int k;
cin >> k;
vector<int> nums(k);
for (int i = 0; i < k; i++) {
cin >> nums[i];
}
vector<unordered_map<int, int>> colContainsList(m);
for (int i = 0; i < m; i++) {
colContainsList[i] = unordered_map<int, int>();
}
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
int val = mat[i][j];
colContainsList[j][val]++;
}
}
unordered_map<int, int> countMap;
for (int num : nums) {
countMap[num]++;
}
unordered_map<int, int> windowCountMap;
int answer = INT_MAX;
int left = 0;
for (int right = 0; right < m; right++) {
for (auto& entry : colContainsList[right]) {
int key = entry.first;
int value = entry.second;
windowCountMap[key] += value;
}
while (check(countMap, windowCountMap)) {
answer = min(answer, right - left + 1);
for (auto& entry : colContainsList[left]) {
int key = entry.first;
int value = entry.second;
windowCountMap[key] -= value;
}
left++;
}
}
cout << (answer != INT_MAX ? answer : -1) << endl;
return 0;
}
时间复杂度：O(M(N+k))。更新win_lst的时间复杂度为O(N)，check()函数所需的时间复杂度为O(k)；滑窗过程一共需要遍历M列，故总的时间复杂度为O(M(N+k))
空间复杂度：O(NM+k)。哈希表所占空间。win_cnt和col_contains_lst所占空间为O(NM)，cnt所占空间为O(k)
华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！
课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化
每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！
60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁
可上全网独家的欧弟OJ系统练习华子OD、大厂真题
可查看链接 大厂真题汇总 & OD真题汇总(持续更新)
绿色聊天软件戳 od1336了解更多