-
Notifications
You must be signed in to change notification settings - Fork 41
/
solution.ts
48 lines (45 loc) · 1.32 KB
/
solution.ts
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
42
43
44
45
46
47
48
function shortestSeq (big: number[], small: number[]): number[] {
const map = new Map<number, number>();
for (let i = 0; i < small.length; i++) {
map.set(small[i], map.has(small[i]) ? map.get(small[i])! + 1 : 1);
}
const curMap = new Map<number, number>();
const M = map.size;
let left = 0;
let right = 0;
let rs = -1;
let re = big.length;
let match = 0;
while (left < big.length) {
while (right < big.length && match < M) {
if (map.has(big[right])) {
const count = curMap.has(big[right]) ? curMap.get(big[right])! + 1 : 1;
const needCount = map.get(big[right]);
if (count === needCount) {
match++;
}
curMap.set(big[right], count);
}
right++;
}
if (match === M) {
const L = right - left;
if (L < re - rs) {
rs = left;
re = right;
}
}
if (curMap.has(big[left])) {
const count = curMap.get(big[left])!;
if (count === map.get(big[left])) {
match--;
}
curMap.set(big[left], count - 1);
}
left++;
}
if (rs === -1) {
return [];
}
return [rs, re - 1, ];
}