使用滑动窗口算法。
由于题目只要求子矩阵的宽度最小,而对子矩阵高度没有限制,因此对于任意连续的列区间,都可以直接选择所有行。问题就转化为:
找一个最短的连续列区间,使这些列中的所有元素能够包含目标数组中的全部元素。
注意目标数组中可能有重复数字,因此需要统计每个数字要求出现的次数。
给定一个矩阵,包含 N∗M 个整数,和一个包含 K 个整数的数组。
现在要求在这个矩阵中找一个宽度最小的子矩阵,要求子矩阵包含数组中所有的整数。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册