LeetCode 76. 最小覆盖子串（Java代码） 滑动窗口框架解题

前往 LeetCode做题

题目的说法有点不完整： 最长覆盖子串要考虑子串中 每个元素出现的次数。（子串并不是无重复的）
输入: S = “bcvrbaa”, T = “aa”
输出: “aa”

思路

这很明显是需要滑动窗口解题，这样可以得到最优值。但是如何写一个滑动窗口确实比较麻烦，通过题解区 labuladong 提供的模板，可以很好地理解滑动窗口。

（滑动窗口）这个算法技巧的思路非常简单，就是维护一个窗口，不断滑动，然后更新答案么。

该算法的大致逻辑如下：

int left = 0, right = 0;

while (right < s.size()) {`
    // 增大窗口
    window.add(s[right]);
    right++;
    
    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

热乎乎的滑动窗口框架

要是做这道题目之前就会这套框架就好了

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    // 字符需要出现的次数
    Map<Character, Integer> need = new HashMap<Character, Integer>();
    // 滑动窗口中字符出现的次数
    Map<Character, Integer> window = new HashMap<Character, Integer>();
    
    for (char c : t.toCharArray()) 
    	needs.put(ch, needs.getOrDefault(ch, 0)+1);
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s.charAt(right);
        // 如果满足条件就将 c移入窗口中，并进行窗口内数据的一系列更新
        if(...)
        	...
        // 右移窗口
        right++;
        

        /*** debug 输出的位置 ***/
        System.out.println("window: ["+left+", "+right+")\n");
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s.charAt(left);
            // 如果满足一定条件，进行窗口内数据的一系列更新，使得退出这个 while循环
            if(...)
            	...
            // 左移窗口
            left++;
        }
    }
}

修改自 LeetCode 题解 labuladong

代码

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || t == null || t.equals("")) {
				return "";
		}
        // 字符需要出现的次数
        Map<Character, Integer> needs = new HashMap<Character, Integer>();
        // 滑动窗口中字符出现的次数
        Map<Character, Integer> window = new HashMap<Character, Integer>();
        for(char ch:t.toCharArray()){
            needs.put(ch, needs.getOrDefault(ch, 0)+1);
        }
        int[] minRange = {Integer.MAX_VALUE, 0, 0};
        int left = 0, right = 0, count = 0;
        while(right < s.length()){
            char ch = s.charAt(right);
            // 如果需要此字符
            if(needs.containsKey(ch)){
                window.put(ch, window.getOrDefault(ch, 0)+1);
                // 如果需求的量被满足了，count++
                if(window.get(ch).compareTo(needs.get(ch)) == 0){
                    count++;
                }
            }
            // 缩小左区域范围
            while(count == needs.size()){
                char c = s.charAt(left);
                if(window.containsKey(c)){
                    window.put(c, window.get(c)-1);
                    if(window.get(c).compareTo(needs.get(c)) < 0){
                        // 此时除去了这个 left处的字符，刚好不满足条件，
                        // 说明此处 left和right是最小的范围
                        if(right - left < minRange[0]){
                            minRange[1] = left;
                            minRange[2] = right;
                            minRange[0] = right - left;
                        }
                        count--;
                    }
                }
                left++;
            }
            right++;
        }
        if (minRange[0] == Integer.MAX_VALUE) {
            return "";
        }
        return s.substring(minRange[1], minRange[2] + 1);
    }
}

速度最快的解法

import java.util.Arrays;

public class Solution {

    public String minWindow(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();

        if (sLen == 0 || tLen == 0 || sLen < tLen) {
            return "";
        }

        char[] charArrayS = s.toCharArray();
        char[] charArrayT = t.toCharArray();

        int[] tFreq = new int[128];
        for (char c : charArrayT) {
            tFreq[c]++;
        }

        // 滑动窗口内部还差多少 T 中的字符，对应字符频数超过不重复计算
        int distance = tLen;
        int minLen = sLen + 1;
        int begin = 0;

        int left = 0;
        int right = 0;
        // [left..right)
        while (right < sLen) {
            char charRight = charArrayS[right];
            if (tFreq[charRight] > 0) {
                distance--;
            }
            tFreq[charRight]--;
            right++;

            // System.out.println(distance + " " + s.substring(left, right));
            while (distance == 0) {
                // System.out.println("左边界收缩 " + distance + " " + s.substring(left, right));
                // System.out.println(tFreq['A'] + "," + tFreq['B'] + "," + tFreq['C']);

                if (right - left < minLen) {
                    minLen = right - left;
                    begin = left;
                }

                char charLeft = charArrayS[left];
                tFreq[charLeft]++;
                if (tFreq[charLeft] > 0) {
                    distance++;
                }
                left++;
            }
        }

        if (minLen == sLen + 1) {
            return "";
        }
        return s.substring(begin, begin + minLen);
    }
}