力扣面试题17.18.最短超串
-
类似76.
-
用哈希表处理短数组 然后遍历长数组
- 找到相同元素 count– –
- 当count==0时进入循环 —— 尽可能缩小区间
-
class Solution {public:vector<int> shortestSeq(vector<int>& big, vector<int>& small) {int n=big.size(),m=small.size();int st=-1,ed=n;unordered_map<int,int> cnt;int count=0; //记录small中元素个数for(auto c:small){if(!cnt.count(c)) count++;cnt[c] ++;}for(int i=0,j=0;i<n;i++){cnt[big[i]] --;if(cnt[big[i]] == 0) count--;while(!count){cnt[big[j]] ++;//说明当前左端点为small中元素 并且big的区间内已不包含if(cnt[big[j]] >0){count++;if(ed - st > i - j) st = j,ed = i;}j ++;}}if(st == -1) return {};else return {st,ed};}};