76. Minimum Window Substring（最小覆盖子串）

题目链接：https://leetcode.com/problems/minimum-window-substring/

方法一：

思路就是用两个HashMap进行存储，一个用于将t字符串中的

所有字符以及相对应的个数存储进来。另一个用于在迭代中比较。

控制两个指针，left和right，先让right一直向右遍历直到map中存够了t字符串中的所有值。

此时将left在向右滑动，直到map中的值不再和t字符串完全匹配。

用一个三个元素的一维数组保存最小覆盖子串长度和left，right下标。

借用一下官方的图：

76. Minimum Window Substring（最小覆盖子串）

AC 23ms Java:

class Solution {
    public String minWindow(String s, String t) {
        if(s.length()==0||t.length()==0)
            return "";
        Map<Character,Integer> dict=new HashMap();
        for(int i=0;i<t.length();i++){
            int value=dict.getOrDefault(t.charAt(i),0);
            dict.put(t.charAt(i),value+1);
        }
        int sum=dict.size();
        int left=0,right=0;
        int count=0;
        int[] ans={-1,0,0};
        Map<Character,Integer> window=new HashMap();
        while(right<s.length()){
            char c=s.charAt(right);
            int value=window.getOrDefault(c,0);
            window.put(c,value+1);
            if(dict.containsKey(c)&&window.get(c).intValue()==dict.get(c).intValue())
                count++;
            while(left<=right&&count==sum){
                c=s.charAt(left);
                if(ans[0]==-1||right-left+1<ans[0]){
                    ans[0]=right-left+1;
                    ans[1]=left;
                    ans[2]=right;
                }
                window.put(c,window.get(c)-1);
                if(dict.containsKey(c)&&window.get(c).intValue()<dict.get(c).intValue())
                    count--;
                left++;
            }
            right++;
        }
        return ans[0]==-1?"":s.substring(ans[1],ans[2]+1);
    }
}

注意：window.get(c).intValue()==dict.get(c).intValue() 这里一定要加上intValue()方法（或者用equals比较）。

因为我们在HashMap中用的是Integer包装类，本质上是对象，在比较的时候会比较堆中的地址。

扩展：Integer比较不要使用==使用equals()或Integer.intValue()

方法二：比较快的一种方法。

思路和方法一相同，只不过这次并不用HashMap存储，而是用128个int型数组存储。

首先对t字符串遍历，每个t字符串中出现过的字符都会在数组中显示它出现过多少次，

然后sum=记录t的长度，接下来right指针向右遍历，如果char rc=s.charAt(right)，array[rc]>0

说明该字符是在t字符串中出现过的，直到right指针停止，此时转向对left指针的判断。

考虑一个例子，（结合下面的AC代码看更好）

s=“AAACBEADC”

t=“AAC”

最初array['A']==2,array['C']==1;

right向右滑动时，到达第三个A，此时的A不应该计入有效的字符，应该到C停止。sum=0；

array['A']=-1;

然后left向右滑动，如果array['A']=0，说明到了有效字符的边界，从而sum++。

AC 2ms 98% Java:

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() == 0 || t.length() == 0) {
            return "";
        }
        int[] array=new int[128];
        for(int i=0;i<t.length();i++){
            array[t.charAt(i)]++;
        }
        int left=0,right=0,head=-1,sum=t.length(),window=Integer.MAX_VALUE;
        while(right<s.length()){
            char rc=s.charAt(right);
            if(array[rc]>0){
                sum--;
            }
            array[rc]--;
            while(sum==0){
                char lc=s.charAt(left);
                if(window>right-left+1){
                    window=right-left+1;
                    head=left;  
                }
                if(array[lc]==0){
                    sum++;
                }
                array[lc]++;
                left++;
            }
            right++;
        }
        return head==-1?"":s.substring(head,head+window);
    }
}

方法三：

对方法一进行优化：

不过个人不建议用其他的库。

import javafx.util.Pair;

class Solution {
    public String minWindow(String s, String t) {

        if (s.length() == 0 || t.length() == 0) {
            return "";
        }

        Map<Character, Integer> dictT = new HashMap<Character, Integer>();

        for (int i = 0; i < t.length(); i++) {
            int count = dictT.getOrDefault(t.charAt(i), 0);
            dictT.put(t.charAt(i), count + 1);
        }

        int required = dictT.size();

        // Filter all the characters from s into a new list along with their index.
        // The filtering criteria is that the character should be present in t.
        List<Pair<Integer, Character>> filteredS = new ArrayList<Pair<Integer, Character>>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (dictT.containsKey(c)) {
                filteredS.add(new Pair<Integer, Character>(i, c));
            }
        }

        int l = 0, r = 0, formed = 0;
        Map<Character, Integer> windowCounts = new HashMap<Character, Integer>();  
        int[] ans = {-1, 0, 0};

        // Look for the characters only in the filtered list instead of entire s.
        // This helps to reduce our search.
        // Hence, we follow the sliding window approach on as small list.
        while (r < filteredS.size()) {
            char c = filteredS.get(r).getValue();
            int count = windowCounts.getOrDefault(c, 0);
            windowCounts.put(c, count + 1);

            if (dictT.containsKey(c) && windowCounts.get(c).intValue() == dictT.get(c).intValue()) {
                formed++;
            }

            // Try and contract the window till the point where it ceases to be 'desirable'.
            while (l <= r && formed == required) {
                c = filteredS.get(l).getValue();

                // Save the smallest window until now.
                int end = filteredS.get(r).getKey();
                int start = filteredS.get(l).getKey();
                if (ans[0] == -1 || end - start + 1 < ans[0]) {
                    ans[0] = end - start + 1;
                    ans[1] = start;
                    ans[2] = end;
                }

                windowCounts.put(c, windowCounts.get(c) - 1);
                if (dictT.containsKey(c) && windowCounts.get(c).intValue() < dictT.get(c).intValue()) {
                    formed--;
                }
                l++;
            }
            r++;   
        }
        return ans[0] == -1 ? "" : s.substring(ans[1], ans[2] + 1);
    }
}

76. Minimum Window Substring（最小覆盖子串）

相关推荐