C++刷leetcode（76. 最小覆盖子串）【滑动窗口】

糖逗

题目描述：

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
说明：

如果 S 中不存这样的子串，则返回空字符串 ""。
如果 S 中存在这样的子串，我们保证它是唯一的答案。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-window-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    string minWindow(string s, string t) {
        map<char, int> need, store;
        for(auto cha : t)need[cha]++;

        int left = 0, right = 0;
        int start = 0, valid = 0;
        int len = INT_MAX;
        while(right < s.size()){
            char temp = s[right];
            right++;

            if(need.count(temp) != 0){
                store[temp]++;
                if(store[temp] == need[temp])valid++;
            }

            while(valid == need.size()){//注意此处的判断
                if(right - left < len){
                    len = right - left;
                    start = left;
                }
                char temp1 = s[left];
                left++;
                if(need.count(temp1)!=0){
                    if(need[temp1] == store[temp1])valid--;
                    store[temp1]--;
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

参考链接：https://leetcode-cn.com/problems ... -yong-si-xiang-by-/

糖逗

相似题目：面试题 17.18. 最短超串
题目描述：

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

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

示例 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shortest-supersequence-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution {
public:
    vector<int> shortestSeq(vector<int>& big, vector<int>& small) {
        map<int, int> need, store;
        for(auto cha : small)need[cha]++;

        int left = 0, right = 0;
        int start = 0, valid = 0;
        int len = INT_MAX;
        //先固定右端再逐渐缩短左端
        while(right < big.size()){
            int temp = big[right];
            right++;
            if(need.count(temp) != 0){
                store[temp]++;
                if(store[temp] == need[temp])valid++;
            }

            while(valid == need.size()){
                if(right - left < len){
                    len = right - left;
                    start = left;
                }

                int temp1 = big[left];
                left++;
                if(need.count(temp1)!=0){
                    if(need[temp1] == store[temp1])valid--;
                    store[temp1]--;
                }
            }
        }
        vector<int>res;
        if(len != INT_MAX)res = {start, start + len - 1};
        return res;
    }
};