题目描述

image-20221125203733786

思路分析

双指针 + hash表

  • 要求一个范围符合要求的答案，可以优先想到双指针
  • 又需要一个包含的要求（长数组包含短数组所有元素），所以需要用hash表来计数
  • cnt代表[i, j]区间中符合要求的元素个数，当cnt == small.size()时
    • 长数组已经包含了短数组所有的元素
    • 但此时可能存在一些不需要的元素，所以要缩小左边界，直到找到符合要求的最短
  • 双指针也可以看成是滑动窗口
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<int> shortestSeq(vector<int>& big, vector<int>& small) {
        unordered_map<int, int> hashS;
        for (auto& v : small) ++hashS[v];
        int n = big.size();
        int cnt = 0;
        int left = -1, right = -1;
        int i = 0, j = 0;
        unordered_map<int, int> hashB;
        while (j < n) {
            int cur = big[j];
            hashB[cur]++;
            if (hashB[cur] <= hashS[cur]) cnt++;
            if (cnt == small.size()) {
                while (i < j && hashB[big[i]] > hashS[big[i]]) {
                    hashB[big[i]]--;
                    i++;
                }
                // cout << "i = " << i << ", j = " << j << endl;
                if (left == -1 || (right - left) > (j - i)) {
                    left = i;
                    right = j;
                }
            }
            j++;
        }
        if (left == -1) return {};

        return {left, right};
    }
};
// 双指针 + hash表

image-20221125203615258