LeetCode-1949 最短超串

📝题目

假设你有两个数组，一个长一个短，短的元素均不相同。找到长数组中包含短数组所有的元素的最短子数组，其出现顺序无关紧要。

返回最短子数组的左端点和右端点，如有多个满足条件的子数组，返回左端点最小的一个。若不存在，返回空数组。

示例 1:

输入:
big = [7,5,9,0,2,1,3,5,7,9,1,1,5,8,8,9,7]
small = [1,5,9]
输出: [7,10]

示例 2:

输入:
big = [1,2,3]
small = [4]
输出: []

限制：
big.length <= 100000
1 <= small.length <= 100000

📝思路

使用一个哈希表（可使用unordered_map）记录当前窗口包含的small数组的元素及每个元素在窗口内出现的次数，使用变量cnt记录窗口内包含的不同元素的个数，当窗口内包含了small数组中所有的元素时，缩小左边界直至窗口恰好包含所有的元素，最后比较并记录最小窗口的左右边界。

📝题解

vector<int> shortestSeq(vector<int>& big, vector<int>& small) {
    int len = big.size(), len2 = small.size();
    if (!len)   return {};

    unordered_map<int, int> m;
    for (int i = 0; i < len2; ++i) {
        m.insert(pair<int, int>(small[i], 0));
    }
    
    int lft = 0, rgt = 0;
    int cnt = 0;
    vector<int> res;
    while (rgt < len) {
        if (m.find(big[rgt]) != m.end()) {
            m[big[rgt]]++;
            if (m[big[rgt]] == 1)   cnt++;
        }
        while (cnt == len2) {
            if (m.find(big[lft]) != m.end()) {
                m[big[lft]]--;
                if (m[big[lft]] == 0)   cnt--;
            }
            if (res.empty()) {
                res.push_back(lft);
                res.push_back(rgt);
            }
            else if (rgt - lft < res[1] - res[0]) {
                res[0] = lft;
                res[1] = rgt;
            }
            lft++;
        }
        rgt++;
    }
    return res;
}