力扣面试题17.18.最短超串

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