中等
相关标签
相关企业提示
假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。
返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。
示例 1：
输入：
big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]
small = [1,5,9]
输出：[7,10]
示例 2：
输入：
big = [1,2,3]
small = [4]
输出：[]
提示：
big.length <= 1000001 <= small.length <= 100000
通过次数
17,981/40.1K
通过率
44.8%
相关企业
提示 1
从蛮力解法开始。
提示 2
一种蛮力解决方案是对于每个起始位置不断向前移动，直到你找到一个包含所有目标字符的子序列为止。
提示 3
另一种对蛮力方法的考虑是，我们取每个起始索引，在目标字符串中寻找每个元素的下一个出现位置。所有这些出现位置的最大值标志着子序列的尾部（该子序列包含所有目标字符）。这个算法的时间复杂度是多少？怎样才能使它更快呢？
提示 4
考虑一下前面解释的蛮力解法。瓶颈在于我们反复查询某个特定字符的下一个出现位置。有办法优化该过程么？你应该能在O(1)时间内完成。
提示 5
你能从每个索引中预先计算一个特定字符的出现位置吗？尝试使用一个多维数组。
提示 6
在得到了预计算的解法之后，考虑一下如何降低空间复杂度。你应该能够将其降低到O(SB)的时间和O(B)的空间（其中B是较大数组的大小，S是较小数组的大小）。
提示 7
另一种考虑方法是：假设你有一个每个元素所在索引的列表。你能找到包含所有元素的第一个子序列吗？你能找到第二个吗？
提示 8
考虑使用堆。
评论 (0)
💡 讨论区规则
1. 请不要在评论区发表题解！
2. 评论区可以发表关于对翻译的建议、对题目的疑问及其延伸讨论。
3. 如果你需要整理题解思路，获得反馈从而进阶提升，可以去题解区进行。
暂无评论
《程序员面试金典（第 6 版）》独家授权
本书是原谷歌资深面试官的经验之作，帮助了许多想要加入脸书、苹果、谷歌等 IT 名企的求职者拿到 Dream offer。本专题的 100+ 编程面试题是在原书基础上精心挑选出来的，帮助你轻松应战 IT 名企技术面试。
© 2025 领扣网络（上海）有限公司
0 人在线