Dx's Tech Notes

3._最小覆盖子串

5 min read

  • 2.25

    • 依旧创建字典，
    • 右指针移动时，判断当前字符是否>0，如果大于 0，则说明是关键字符，计数器+1， 无论如何当前字符字典内 -1
    • 如果当计数器是等于目标字符串长度，就开始左指针移动，如果当前字符等于 0即为关键字符，少一个都不行，就 count—，无论如何当前字符字典内+1
    • 用 start 和 minL，来截取结果字符串

  • 2.6

    • 两个阶段 a. 先移动右边界，如果需要，计数器+1。不管怎样，字典-1。右指针右移 b.如果窗口到位了，移动左指针，左边的数是需要的话。不管怎样字典+1。左指针右移
      • 记得更新 minL 值和保存 start 以返回截取子串的位置

  • 1.23

    • 注意 count，start 和 minLen 参数

核心思路：“伸缩法”

我们可以把滑动窗口想象成一个 “手风琴” 或者 “毛毛虫”：

  1. 向右扩张 (Right)：如果不满足条件（还没包含 t 中所有字符），right 指针一直往右跑，吃进更多的字符，直到满足条件为止。
  2. 向左收缩 (Left)：一旦满足条件了（当前窗口包含了 t 的所有字符），left 指针就开始往右缩，试图剔除多余的字符，寻找最小的长度。直到窗口不再满足条件，然后重新回到第 1 步。
class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0) {
            return "";
        }
 
        // 1. 欠账表：记录我们需要什么字符，以及需要多少个
        // ASCII 码只有 128 个，用数组比 HashMap 快
        int[] need = new int[128];
        for (char c : t.toCharArray()) {
            need[c]++;
        }
 
        // 2. 定义滑动窗口的边界和核心变量
        int left = 0, right = 0;
        int count = 0; // 记录当前窗口里已经凑齐了 t 中的多少个字符
        
        // 记录最小覆盖子串的起始位置和长度
        int minLen = Integer.MAX_VALUE;
        int start = 0;
 
        // 3. 开始滑动
        while (right < s.length()) {
            char c = s.charAt(right); // 即将移入窗口的字符
 
            // 如果这个字符是 t 需要的（need[c] > 0），那我们的“有效计数”就加 1
            if (need[c] > 0) {
                count++;
            }
            // 无论是不是需要的，账单都要减 1
            // 如果是需要的，从 1 变 0；如果是多余的，从 0 变 -1
            need[c]--;
            
            // 窗口右移
            right++;
 
            // 4. 当 count == t.length() 时，说明当前窗口已经包含了 t 的所有字符
            // 这时候我们需要通过移动 left 来缩小窗口，找最小值
            while (count == t.length()) {
                // 更新最小子串的记录
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }
 
                // 准备移出窗口的字符
                char d = s.charAt(left);
                
                // 恢复账单：移出去了，如果它本来是需要的字符，那账单得加回来
                // 注意：只有当 need[d] == 0 时，说明它是关键字符（非富余字符）
                // 移出它会导致窗口不合格，所以 count--
                if (need[d] == 0) {
                    count--;
                }
                
                // 账单加回来（负数变 0，0 变正数）
                need[d]++;
                
                // 窗口左移
                left++;
            }
        }
 
        // 如果 minLen 没变过，说明没找到
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

Graph View

Backlinks