力扣面试题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}; } };