最短超串
题目描述
假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。
返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。
示例 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
解法：
滑动窗口，以下几种情况需要移动左边界：
big[lo]不在small中big[lo]在 lo~hi 之间出现了多次
class Solution {
public:
vector<int> shortestSeq(vector<int>& big, vector<int>& small) {
unordered_set<int> small_set(small.begin(), small.end());
unordered_map<int, int> window;
cout << big.size();
int lo = 0;
int min_len = big.size()+1;
int min_lo = 0;
for(int hi=0;hi<big.size();hi++){
if(small_set.count(big[hi])){
window[big[hi]]++;
}
while(lo < hi) {
int n = big[lo];
if (small_set.count(n) == 0) {
lo++;
} else if (window.find(n) != window.end() && window[n] > 1) {
lo++;
window[n]--;
}else{
break;
}
}
if(window.size() == small.size() && (hi - lo + 1) < min_len){
min_len = hi - lo + 1;
min_lo = lo;
}
}
if(min_len == big.size()+1){
return {};
}else{
return {min_lo, min_lo + min_len - 1};
}
}
};