[算法系列之二十二]包含T全部元素的最小子窗口

今天药忘吃喽~ 2023-06-19 03:00 27阅读 0赞

**题目描述**

给定一个包含一系列字符的集合T和字符串S,请在字符串S中找到一个最小的窗口，这个窗口中必须包含T中的所有字符。   
例如,   
S = “ADOBECODEBANC”   
T = “ABC”

最小窗口是“BANC”

**分析**

这是一个有趣的问题,这个有趣的问题有多种方法来解决，最好的方法是非常简单，美丽的。   
在这篇文章中,我首先说明了一个方法,是我第一次遇见这个问题时想到的。我的第一个方法有点复杂,同时也不是最好的解决方案(时间复杂度为O(NlgM))。在这篇文章的后面中,我介绍一个比较好的方法,时间复杂度为O(N)。   
**Hint:**   
使用上面的示例中S =“ADOBECODEBANC”，S =“ABC”,我们可以很容易地找到第一个窗口“ADOBEC”，包含了T中所有元素。另一个可能的候选者是“ADOBECODEB A”。事实上,我们应该跳过这个,因为在这个窗口中存在一个子窗口“CODEBA”，既短又满足约束条件。最后考虑的一个窗口是“BANC”,这也是最小的窗口。

为了有效地解决这个问题,下面我们需要考虑的两个关键点:

> 1.  我们如何确定一个特定的窗口包含T ?(最理想的情况是O(1)时间)。
> 2.  我们如何有效的选择所有窗口?(最理想的情况是不包括含有子窗口的那些窗口)。

我们绝对需要哈希表（Hash Table）的帮助。哈希表能在O(1)时间内告诉我们一个字符是否在T 中。

**O(N lg M) 方法**:

当我第一次遇到这一问题,我想到了另一个表,记录字符上次出现的位置。也就是说,当我第一次看到字符’A‘,我记录它的位置是0。我每次再见到’ A ‘,我就用新位置代替它原先的位置。这种方法虽然很简单,但是缺陷也很明显。请注意,T不包含重复的字符吗?如果T包含了重复的字符,如“AABC”,这种方法就不能使用了。

在这种情况下,补救措施是维持一个队列(而不是表),T中每个不同字符对应一个队列（例如：字符A对应一个队列，字符B对应一个队列。。。）。例如,假设T =“AABC”,当你第一次遇到“A”,把它的所在位置放入“A”队列中(最初是空的)。当你再次遇到“A ”时,把它的位置放入“A”队列末尾。第三次遇到“A”时,弹出第一个元素,并把这次遇到的A所在位置放入“A”队列末尾。通过弹出元素,我们不包括那些包含子窗口的窗口。这种方法很有效,但困难是双重的:

> 1.  我们没有办法从队列本身直接确定窗口的开始和结束位置。一个最自然的方法是扫描整个队列得到最小值和最大值。我们如何确定这个窗口是否满足约束条件呢?我们不得不扫描整个队列来检查所有队列大小总和是否等于T的长度。

我解决上述问题的方法是维护一个sorted map,它映射到每一个字符。这样我们能在O(1)时间内获取最小值和最大值的位置。但这样做会花费额外的时间。每次你从队列中弹出一个元素,你不得不通过删除相应的元素和插入一个新元素来更新map。检查窗口是否满足约束条件,我们必须查看map的大小,如果map的大小等于T的长度就代表找到一个有效的窗口。

这个方法的时间复杂度是O(N lg M),其中N是S的长度,和M是T的长度。额外的lgM是由于在map中删除和插入一个元素的额外花费，每个最坏情况花费O(lgM)时间。（注意,M是map的最大大小。）

/*---------------------------------------------
    *   日期：2015-02-24
    *   作者：SJF0115
    *   题目: 22.包含T全部元素的最小子窗口
    *   来源：算法系列
    *   博客：
    -----------------------------------------------*/
    #include <iostream>
    #include <map>
    #include <queue>
    #include <climits>
    #include <algorithm>
    using namespace std;
    
    bool MinWindow(string s,string t,int &startWin,int &endWin){
        int slen = s.size();
        int tlen = t.size();
        if(slen <= 0 || tlen <= 0){
            return false;
        }//if
        // 存储T中不同字符的总数
        int needFind[256] = {0};
        for(int i = 0;i < tlen;++i){
            ++needFind[t[i]];
        }//for
        // 不在T中的元素设置为-1
        for(int i = 0; i < 256;++i){
            if(needFind[i] == 0){
                needFind[i] = -1;
            }//if
        }//for
        int minWinLen = INT_MAX;
        // 队列数组，每个不同的字符都对应一个队列
        queue<int> q[256];
        // 第一个元素和最后一个元素表明了窗口的开始和结束位置
        map<int,char> m;
        int val;
        for(int i = 0;i < slen;++i){
            val = s[i];
            // 跳过不在T中的元素
            if(needFind[val] == -1) {
                continue;
            }//id
            // 字符放入队列
            if(q[val].size() < needFind[val]) {
                q[val].push(i);
                m[i] = val;
            }//if
            // 取代队列中的字符，更新map中对应元素
            else{
                int idxToErase = q[val].front();
                map<int,char>::iterator it = m.find(idxToErase);
                m.erase(it);
                m[i] = val;
                q[val].pop();
                q[val].push(i);
            }//else
            if(m.size() == tlen){
                int end = m.rbegin()->first;
                int start = m.begin()->first;
                int winLen = end - start + 1;
                if (winLen < minWinLen) {
                    minWinLen = winLen;
                    startWin = start;
                    endWin = end;
                }//if
            }//if
        }//for
        return (m.size() == tlen);
    }
    
    int main() {
        string s("acbbaca");
        string t("aba");
        int start,end;
        bool result = MinWindow(s,t,start,end);
        if(result){
            cout<<s.substr(start,end-start+1)<<endl;
        }//if
        else{
            cout<<"未找到"<<endl;
        }//else
        return 0;
    }

**O(N)方法：**

注意到上面的思路是非常复杂的。它使用了一个哈希表,一个队列还有一个sorted map。在面试过程中,给出的问题往往是比较短的，解决方案通常在50行代码左右。所以你有必要大声说出你在想什么,时刻保持与面试官进行沟通。检查你的方法是否是没有必要的复杂,他/她可以给你指导。最不好的就是就是你被困在一点,什么也不说。

为了阐述这个思路,我使用一个不同上面的例子:S = “acbbaca”,T = “aba”。这个**思路**主要是遍历S时使用了两个指针begin和end(窗口开始和结束位置)和两个数组(needToFind 和 hasFound)。needToFind存储T中不同字符的总数，hasFound存储到目前为止遇到过的不同字符的总数。我们也使用一个count变量来存储到目前为止遇到过的T中字符总数(当hasFound\[x\]超过needToFind\[x\]时不用计数)。当count等于T的长度时,我们就找到了一个有效的窗口。

每次我们向前移动end指针(指向一个元素x),我们会使hasFound\[x\]加一。如果hasFound\[x\]是小于或等于needToFind\[x\]时count加一。为什么?当满足约束条件(即count等于T的大小),在满足约束的条件下，我们开尽可能的向右移动begin指针。

我们如何检查是否满足约束条件呢?假设begin指向一个元素x,我们检查hasFound\[x\]是否大于needToFind\[x\]。如果是,我们可以使hasFound\[x\]减一,在不破坏约束条件的前提下向前移动begin指针。相反,如果不是,我们立即停止向前移动begin指针，以防破坏约束条件。

最后,我们检查最小窗口长度是否小于当前的最小窗口长度。如果不是则更新最小窗口长度。

本质上,该算法找到满足约束的第一个窗口后,仍然继续保持约束条件。

![20150223225421332][]

（1） S = “acbbaca” T = “aba“

![20150223225457027][]

（2）第一个找到最小的窗口。我们无法向前移动begin指针当hasFound\[‘a’\]== needToFind\[‘a’\]= = 2。向前移动意味着打破约束。

![20150223225828501][]

（3）第二个窗口。begin指针仍然指向第一个元素“a”。hasFound\[’ a ‘\]（3）大于needToFind\[‘a’\]（2）。我们使hasFound\[’ a ‘\],向右移动begin指针。

![20150223230153517][]

（4）我们跳过元素c，因为它不在T中。现在begin指针指向元素b。hasFound\[b\]（2）大于needToFind\[b\]（1）。我们使hasFound\[b\]减一,同时向右移动begin指针。

![20150223230516751][]

（5）begin指针现在指向下一个元素b。hasFound\[b\]（1）等于needToFind\[b\]（1）。我们立即停止,这是我们新发现的最小的窗口。

begin指针和end指针最坏情况下向前移动至多N步（N 是字符串S的长度），加起来是2N时间，因此时间复杂度是O(N)。

/*---------------------------------------------
    *   日期：2015-02-24
    *   作者：SJF0115
    *   题目: 22.包含T全部元素的最小子窗口
    *   来源：算法系列
    *   博客：
    -----------------------------------------------*/
    #include <iostream>
    #include <climits>
    #include <algorithm>
    using namespace std;
    
    // Returns false if no valid window is found. Else returns
    // true and updates start and end with the
    // starting and ending position of the minimum window.
    bool MinWindow(string s,string t,int &startWin,int &endWin){
        int slen = s.size();
        int tlen = t.size();
        if(slen <= 0 || tlen <= 0){
            return false;
        }//if
        // 存储T中不同字符的总数
        int needFind[256] = {0};
        for(int i = 0;i < tlen;++i){
            ++needFind[t[i]];
        }//for
        // 存储到目前为止遇到过的不同字符的总数
        int hasFound[256] = {0};
        // 存储到目前为止遇到过的T中字符总数
        int count = 0;
        int minWin = INT_MAX;
        int endEle;
        for(int start = 0,end = 0;end < slen;++end){
            endEle = s[end];
            // 剪枝 无用字符(T中字符为有用字符)
            if(needFind[endEle] == 0){
                continue;
            }//if
            ++hasFound[endEle];
            if(hasFound[endEle] <= needFind[endEle]){
                ++count;
            }//if
            // 找到一个有效窗口
            if(count == tlen){
                int begEle = s[start];
                // 满足：字符为无用字符，begEle元素找多了 start指针才向右移动
                while(needFind[begEle] == 0 || hasFound[begEle] > needFind[begEle]){
                    if(hasFound[begEle] > needFind[begEle]){
                       --hasFound[begEle];
                    }//if
                    ++start;
                    begEle = s[start];
                }//while
                // 更新最小窗口
                int curWin = end - start + 1;
                if(curWin < minWin){
                    minWin = curWin;
                    startWin = start;
                    endWin = end;
                }//if
            }//if
        }//while
        return (count == tlen);
    }
    
    int main() {
        string s("ADOBECODEBANC");
        string t("ABC");
        int start,end;
        bool result = MinWindow(s,t,start,end);
        if(result){
            cout<<s.substr(start,end-start+1)<<endl;
        }//if
        else{
            cout<<"未找到"<<endl;
        }//else
        return 0;
    }

本文原文地址：[https://blog.csdn.net/SunnyYoona/article/details/43924715][https_blog.csdn.net_SunnyYoona_article_details_43924715]

[20150223225421332]: https://img-blog.csdn.net/20150223225421332
[20150223225457027]: https://img-blog.csdn.net/20150223225457027
[20150223225828501]: https://img-blog.csdn.net/20150223225828501
[20150223230153517]: https://img-blog.csdn.net/20150223230153517
[20150223230516751]: https://img-blog.csdn.net/20150223230516751
[https_blog.csdn.net_SunnyYoona_article_details_43924715]: https://blog.csdn.net/SunnyYoona/article/details/43924715