golang 解法, 执行用时: 72 ms, 内存消耗: 9.9 MB, 提交时间: 2022-11-30 22:19:44

func shortestSeq(big []int, small []int) []int {
    left, right := 0, 0
    l, r := 0, 0
    length := 1 << 31 - 1
    match := 0

    smallMap := make(map[int]int)
    bigsubMap := make(map[int]int)

    for _, s := range small {
        smallMap[s]++
    }
    for right < len(big) {
        if time, ok := smallMap[big[right]]; ok {
            bigsubMap[big[right]] ++

            if bigsubMap[big[right]] == time {
                match++
            }
        }

        for match == len(smallMap) {

            if right - left < length {
                l = left
                r = right

                length = right - left
            }

            if _, ok := smallMap[big[left]]; !ok {
                left ++
                continue
            }
            bigsubMap[big[left]] --

            if bigsubMap[big[left]] < smallMap[big[left]] {
                match --
            }

            left ++

        }
        right ++


    }

    if l == 0 && r == 0 {
        return nil
    }

    return []int{l, r}
}

python3 解法, 执行用时: 132 ms, 内存消耗: 29.3 MB, 提交时间: 2022-11-30 22:18:02

class Solution:
    def shortestSeq(self, big: List[int], small: List[int]) -> List[int]:
        import collections
        cnt = collections.Counter(small)
        l = 0
        n = 0
        ans = []
        for r,ch in enumerate(big):
            if ch not in cnt:   #不在cnt 继续
                continue
            cnt[ch] -= 1         #在cnt
            if cnt[ch] == 0:
                n += 1          #统计n
            while big[l] not in cnt or cnt[big[l]] < 0: #移动左指针：big[l]不在cnt，或者big[l]出现不止一次
                if cnt[big[l]] < 0:
                    cnt[big[l]] += 1    #如果出现不止一次， 左指针右移，并加一
                l += 1
            if n == len(cnt):          #如果符合题目条件：
                if not ans or (ans[1]-ans[0]) > r - l:   #找最小串
                    ans = []
                    ans.append(l)
                    ans.append(r)
        return ans

cpp 解法, 执行用时: 84 ms, 内存消耗: 46.4 MB, 提交时间: 2022-11-30 22:17:36

class Solution {
public:
    vector<int> shortestSeq(vector<int>& big, vector<int>& small) {
        int n = big.size();
        vector<int> res;
        // need：记录滑动窗口内需要覆盖的数字，及其对应的个数
        unordered_map<int, int> need;
        // diff：记录滑动窗口一共需要覆盖的数字个数
        int minLen = n, diff = 0;
        // 数据预处理：统计需要覆盖的字符有多少个
        for (auto& e : small) {
            need[e]++;
            diff++;
        }

        // 滑动窗口：l指向窗口左边界，r指向窗口右边界
        int l = 0, r = 0;
        for (; r < n; ++r) {
            // need中存在，diff减一
            if (need.find(big[r]) != need.end() && --need[big[r]] >= 0) --diff;
            // 如果diff = 0，收缩窗口，左指针右移
            while (diff == 0) {
                if (r - l < minLen) {
                    minLen = r - l;
                    res = {l, r};
                }
                if (need.find(big[l]) != need.end() && ++need[big[l]] > 0) ++diff;
                ++l;
            }
        }

        return res;
    }
};