题目分析

这个题目和Leetcode76题是类似的，只不过第76题是字符串，而这个题目是数组。当时做那个题目的时候，还没有想记录自己的刷题过程，因此那个题目没有写博客，今天做了这个题目，发现似曾相识，给小伙伴们介绍一下这样的题目应该如何求解。

双指针

这个题目肯定是不能使用暴力法进行求解的，就算是使用DP来解，也要$O(n^2)$的时间复杂度，对于1e5这个量级的数据，我们只能使用$O(nlog(n))$以下的算法进行求解。

双指针是求解这个问题的最优方案，也可以称之为滑动窗口(Sliding Window)。什么意思呢？就是建立左右两个指针，其中左右指针中间的元素称为窗口，因为左右指针在不断右移，因此称为滑动窗口。

我们先找到满足条件的右窗口，然后再收缩左窗口。如果左窗口不满足条件，说明此时左右窗口处恰好满足其中一个解。然后我们继续右移有窗口，到下一次满足条件的位置，然后再次收缩左窗口，直到右窗口到达数组的边界。

在滑动过程中，我们要用哈希表记录small中每一个元素出现的次数。如果次数都大于1，说明满足条件，右窗口停止滑动，开始滑动左窗口，如果次数有一个等于0，那么不满足条件，左窗口停止，开始滑动右窗口。

算法的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

#include<iostream>
#include<vector>
#include<unordered_map>

using namespace std;

class Solution {
public:
    vector<int> shortestSeq(vector<int>& big, vector<int>& small) {
        unordered_map<int, int> dict;
        for (int x : small) { dict[x] = 0; }
        int left = 0, right = 0, cnt = 0, bigLen = big.size(), smallLen = small.size();
        vector<int> res = { -1, bigLen };
        while (right < bigLen) {
            while (right < bigLen && cnt < smallLen) {
                int curVal = big[right++];
                if (dict.count(curVal) && !(dict[curVal]++)) { cnt++; }
            }
            while (left <= right && cnt == smallLen) {
                int curVal = big[left++];
                if (dict.count(curVal) && !(--dict[curVal])) { cnt--; }
            }
            if (res[1] - res[0] > right - left) { res = { left - 1, right - 1 }; }
        }
        return res[0] >= 0 ? res : vector<int>();
    }
};

刷题总结

滑动窗口是一个非常非常重要的知识点，和单调栈，单调队列类似，都是线性的时间复杂度，是面试笔试中的常客，小伙伴们要多多留心。