Amazon OA 面试真题解析：最短覆盖子数组（Shortest Subarray Covering a Set）

Write a program which takes an array of strings and a set of strings, and returns the starting and ending indices of a shortest subarray of the given array that covers the set, i.e., contains all strings in the set.

Example:

<apple, banana, apple, apple, dog, cat, apple, dog, banana, apple, cat, dog>
Set: <banana, cat>

Smallest subarray starts at 8, ends at 10.

这道题要求在字符串数组中找到一个最短连续子数组，使它包含给定集合中的所有字符串。典型做法是使用滑动窗口配合哈希表 / 计数器：右指针不断扩展窗口收集目标词，满足覆盖条件后再移动左指针尽量缩小窗口，并在过程中维护最优答案。示例中需要同时覆盖 <code>banana</code> 和 <code>cat</code>，因此最终找到的最短区间是 <code>[8, 10]</code>。这类题的核心是“覆盖型窗口”与最小区间更新。