最小覆盖子串

原题链接

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。

思路

创建一个窗口[l,r]
一直右移r直到窗口覆盖子串(覆盖则判断窗口是否最小并记录)
右移l(覆盖则判断窗口是否最小并记录)，若窗口无法覆盖子串回到步骤2

细节：

如何判断窗口是否覆盖子串，设计一个cnt来记录当前窗口有多少字母在子串里，当cnt==子串长度时，则覆盖。
如何判断当前字母是否是子串需要，使用map来存子串中每个字母需要的数量，若大于0，则表明还需要。
本题只用记录字母，因此可以直接用vector来存。
r=-1; r<s.size()
- s.size() 是无符号整数（size_t）
- r = -1 被隐式转换为无符号整数-1的二进制补码表示是全1（如 0xFFFFFFFF），转换成 size_t 后变成一个巨大的正数
- r < s.size() 实际上是 2^32-1 < 5，是 false，无法进入循环

时间复杂度 O(n+m)

代码

c++

class Solution {
public:
    string minWindow(string s, string t) {
        string ans = "";
        vector<int> ve(128,0); //当要记录的数据是字母时，可以不使用map,直接用vector
        for(auto c:t) ve[c]++; //ve[i]大于0，即说明当前区间还需要多少字母i
        int ansl=0,ansr=1e5+10,cnt=t.size(); //使用cnt记录当前子串覆盖了多少，而不用单独检查每个字母
        int l=0,r=-1;//r=-1保证刚开始第一个0也可以判断到
        int sz = s.size(); //直接s.size()是unsigned数据类型，如果直接-1<s.size()，-1会强制类型转换成2^32-1
        for(l,r;r<sz;)
        {
            while(r<sz&&cnt!=0) //r一直右移，直到找到一个区间lr，使得覆盖子串（cnt==0）
            {
                r++;//移动后判断当前位
                if(ve[s[r]]>0) cnt--;
                ve[s[r]]--;
            }
            if(!cnt&&r-l<ansr-ansl) ansl=l,ansr=r;  //若cnt==0，记录
            while(l<=r&&cnt==0) //l右移，找到，当无法覆盖子串时停止右移。
            {
                if(ve[s[l]]==0) cnt++; //l右移后，判断失去的字母是不是被需要的，若不被需要，则在之前r右移时已经被减少至负数
                ve[s[l]]++;
                l++;//判断当前位后移动
                if(!cnt&&r-l<ansr-ansl) ansl=l,ansr=r; //l每右移一次都要做一次判断，因为可能区间变小
            }
        }
        return ansr == 1e5+10 ? "" : s.substr(ansl,ansr-ansl+1);
    }
};

最小覆盖子串 ​

题目 ​

思路 ​

代码 ​

最小覆盖子串

题目

思路

代码