Problem:面试题 17.18. 最短超串

思路：统计统计滑动窗口内的small数组的元素出现的个数记为k,如果k==small.size(),那么说明此时窗口里面已经包含所有的small元素了接下来可以尝试着缩小窗口的左端点，顺便更新答案。
ps:楼楼脑子短路了，以为滑动窗口内每个元素只能出现一次…然后就是和题目对目了。
相似题
Accode:

class Solution {
public:
    vector<int> shortestSeq(vector<int>& big, vector<int>& small) {
        if (big.size() < small.size())
            return vector<int>();
        vector<int> ans(1, 0);
        ans.push_back(1e9 + 1);
        int len = big.size();
        unordered_map<int, int> cnt;
        unordered_map<int, int> sum;
        int flag = 0;
        for (auto it : small) {
            cnt[it]++;
        }
        for (int i = 0, j = 0; i < len; i++) {
            sum[big[i]]++;
            if (sum[big[i]] == 1 && cnt.find(big[i]) != cnt.end())
                flag++;
            while (cnt.find(big[i]) != cnt.end() && j < i &&
                   flag == small.size()) {
                if (cnt.find(big[j]) == cnt.end()) {
                    j++;
                } else {
                    if (sum[big[j]] > 1) {
                        sum[big[j]]--;
                        j++;
                    }
                    else break;
                }
            }
            while (j < i && cnt.find(big[j]) == cnt.end())
                j++;
            if (flag == small.size() && i - j < ans[1] - ans[0]) {
                ans[0] = j, ans[1] = i;
            }
        }
        if (ans[1] == 1e9 + 1)
            return vector<int>();
        return ans;
    }
};

时间复杂度：$o(n)$看着多重循环，然而i,j最多执行n次