72.Minimum Window Substring（最小子串窗口）

Level：

Hard

题目描述：

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC"

Output: "BANC"

Note:

If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

思路分析：

知识点：滑动窗口

关键点一：像这种找子串的可以使用滑动窗口Sliding Window来做。这个窗口由left和right来约束[left,right]这个闭区间，刚开始知识left=right=0，然后left不变，right不断增长，直到到达某个值，left和right一起增长，这样就实现了窗口的创建和向下滑动。

关键点二：对于p中出现的字符以及次数需要记下来。可以使用一个数组ascaiiNums，长度为256，是因为ascaii一共只有256个，初始化的值表示角标对应的ascaii字符在p中出现的次数，那么没有出现过的就是0.之后如果s中出现过该字符，那么数组对应位置的值就减一。如果减之后的值大于等于0，就说明p中该字符出现了一次，这时p中未出现的字符数量count就减一。之所以要判断是>=0,是因为如果数组中原来的值是0（说明p中没有出现），那么减一后就成了负的，这种情况下p中剩下未出现的字符的count数值保持不变。如果count的值为0，说明p中的字符全出现了，找到一个符合条件的子串，left就是子串的首地址。之后要向右滑动窗口，移动的方法是left++,right++，更新p中未出现的字符个数count。

代码：

public class Solution{

    public String minWindow(String s,String t){

        if(s==null||t==null||s.length()==0||t.length()==0)

            return null;

        String res="";

        int []map=new int [256];

        int match=t.length();

        int left=0; //窗口左端

        for(int i=0;i<t.length();i++){

            map[t.charAt(i)]++;

        }

        int minlen=Integer.MAX_VALUE;

        for(int i=0;i<s.length();i++){//i充当窗口的右端

            map[s.charAt(i)]--;

            if(map[s.charAt(i)]>=0)

                match--;         //证明该字符在t中

            if(match==0){

                while(map[s.charAt(left)]<0){

                    map[s.charAt(left)]++;

                    left++; //这些字符都不存在与t中

                }

                if((i-left+1)<minlen){//更新最短子串

                    minlen=i-left+1;

                    res=s.substring(left,i+1);

                }

            match++; //寻找下一个包含t的串

            map[s.charAt(left)]++;

            left++;

            }

        }

        return minlen==Integer.MAX_VALUE?"":res;

    }

}

巴特西

72.Minimum Window Substring（最小子串窗口）

Level：

题目描述：

思路分析：

代码：

最新文章

热门文章