题目描述
假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。
返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。
示例 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
解法
方法一：哈希表 + 双指针
我们定义两个哈希表，其中哈希表 $need$ 用于存储数组 $small$ 中的元素及其出现次数，哈希表 $window$ 用于存储当前滑动窗口中的元素及其出现次数。另外，我们用变量 $cnt$ 记录当前未满足条件的元素个数，用变量 $mi$ 记录最短子数组的长度，用变量 $k$ 记录最短子数组的左端点。
我们用双指针 $j$ 和 $i$ 分别表示滑动窗口的左右端点，初始时，$j$ 和 $i$ 均指向数组 $big$ 的第一个元素。我们先移动右指针 $i$，将 $big[i]$ 加入到 $window$ 中，如果 $window[big[i]]$ 的值小于等于 $need[big[i]]$ 的值，说明当前滑动窗口中包含数组 $small$ 中的一个元素，令 $cnt$ 减一。当 $cnt$ 的值等于 $0$ 时，说明当前滑动窗口中包含数组 $small$ 中的所有元素，此时我们移动左指针 $j$，将 $big[j]$ 从 $window$ 中减去，如果 $window[big[j]]$ 的值小于 $need[big[j]]$ 的值，说明当前滑动窗口不再包含数组 $small$ 中的所有元素，令 $cnt$ 加一。在滑动窗口移动的过程中，我们更新 $mi$ 和 $k$ 的值。
时间复杂度 $O(m + n)$，空间复杂度 $O(m + n)$。其中 $m$ 和 $n$ 分别是数组 $big$ 和 $small$ 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | class Solution:
def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:
need = Counter(small)
window = Counter()
cnt, j, k, mi = len(small), 0, -1, inf
for i, x in enumerate(big):
window[x] += 1
if need[x] >= window[x]:
cnt -= 1
while cnt == 0:
if i - j + 1 < mi:
mi = i - j + 1
k = j
if need[big[j]] >= window[big[j]]:
cnt += 1
window[big[j]] -= 1
j += 1
return [] if k < 0 else [k, k + mi - 1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | class Solution {
public int[] shortestSeq(int[] big, int[] small) {
int cnt = small.length;
Map<Integer, Integer> need = new HashMap<>(cnt);
Map<Integer, Integer> window = new HashMap<>(cnt);
for (int x : small) {
need.put(x, 1);
}
int k = -1, mi = 1 << 30;
for (int i = 0, j = 0; i < big.length; ++i) {
window.merge(big[i], 1, Integer::sum);
if (need.getOrDefault(big[i], 0) >= window.get(big[i])) {
--cnt;
}
while (cnt == 0) {
if (i - j + 1 < mi) {
mi = i - j + 1;
k = j;
}
if (need.getOrDefault(big[j], 0) >= window.get(big[j])) {
++cnt;
}
window.merge(big[j++], -1, Integer::sum);
}
}
return k < 0 ? new int[0] : new int[] {k, k + mi - 1};
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32 | class Solution {
public:
vector<int> shortestSeq(vector<int>& big, vector<int>& small) {
int cnt = small.size();
unordered_map<int, int> need;
unordered_map<int, int> window;
for (int x : small) {
need[x] = 1;
}
int k = -1, mi = 1 << 30;
for (int i = 0, j = 0; i < big.size(); ++i) {
window[big[i]]++;
if (need[big[i]] >= window[big[i]]) {
--cnt;
}
while (cnt == 0) {
if (i - j + 1 < mi) {
mi = i - j + 1;
k = j;
}
if (need[big[j]] >= window[big[j]]) {
++cnt;
}
window[big[j++]]--;
}
}
if (k < 0) {
return {};
}
return {k, k + mi - 1};
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30 | func shortestSeq(big []int, small []int) []int {
cnt := len(small)
need := map[int]int{}
window := map[int]int{}
for _, x := range small {
need[x] = 1
}
j, k, mi := 0, -1, 1<<30
for i, x := range big {
window[x]++
if need[x] >= window[x] {
cnt--
}
for cnt == 0 {
if t := i - j + 1; t < mi {
mi = t
k = j
}
if need[big[j]] >= window[big[j]] {
cnt++
}
window[big[j]]--
j++
}
}
if k < 0 {
return []int{}
}
return []int{k, k + mi - 1}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28 | function shortestSeq(big: number[], small: number[]): number[] {
let cnt = small.length;
const need: Map<number, number> = new Map();
const window: Map<number, number> = new Map();
for (const x of small) {
need.set(x, 1);
}
let k = -1;
let mi = 1 << 30;
for (let i = 0, j = 0; i < big.length; ++i) {
window.set(big[i], (window.get(big[i]) ?? 0) + 1);
if ((need.get(big[i]) ?? 0) >= window.get(big[i])!) {
--cnt;
}
while (cnt === 0) {
if (i - j + 1 < mi) {
mi = i - j + 1;
k = j;
}
if ((need.get(big[j]) ?? 0) >= window.get(big[j])!) {
++cnt;
}
window.set(big[j], window.get(big[j])! - 1);
++j;
}
}
return k < 0 ? [] : [k, k + mi - 1];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41 | class Solution {
func shortestSeq(_ big: [Int], _ small: [Int]) -> [Int] {
let needCount = small.count
var need = [Int: Int]()
var window = [Int: Int]()
small.forEach { need[$0, default: 0] += 1 }
var count = needCount
var minLength = Int.max
var result = (-1, -1)
var left = 0
for right in 0..<big.count {
let element = big[right]
if need[element] != nil {
window[element, default: 0] += 1
if window[element]! <= need[element]! {
count -= 1
}
}
while count == 0 {
if right - left + 1 < minLength {
minLength = right - left + 1
result = (left, right)
}
let leftElement = big[left]
if need[leftElement] != nil {
window[leftElement]! -= 1
if window[leftElement]! < need[leftElement]! {
count += 1
}
}
left += 1
}
}
return result.0 == -1 ? [] : [result.0, result.1]
}
}
|