最小覆盖子串

理解题目：

题目要求在给定的字符串 s 和 t 中，找到包含字符串 t 中所有字符的最小窗口子串。

代码实现：

import java.util.HashMap;
import java.util.Map;

public class MinimumWindowSubstring {
    // 最小覆盖子串
    public String minWindow(String s, String t) {
        // 检查输入的字符串是否为空，以及字符串 s 的长度是否小于字符串 t 的长度，如果是则直接返回空字符串。
        if (s == null || t == null || s.length() == 0 || t.length() == 0 || s.length() < t.length()) {
            return "";
        }

        // 统计字符串 t 中每个字符的频率
        Map<Character, Integer> targetFreq = new HashMap<>();
        for (char c : t.toCharArray()) {
            targetFreq.put(c, targetFreq.getOrDefault(c, 0) + 1);
        }

        // 初始化左右指针，记录最小覆盖子串的起始位置和最小覆盖子串的长度，以及匹配字符数量。
        int left = 0, right = 0;
        int minLen = Integer.MAX_VALUE;
        int start = 0;
        int matchCount = 0;

        // 使用双指针维护滑动窗口，遍历字符串 s
        while (right < s.length()) {
            // 如果当前字符是字符串 t 中的字符，则在 targetFreq 中相应字符频率减1，如果频率大于等于0，增加匹配字符数量。
            char rightChar = s.charAt(right);
            if (targetFreq.containsKey(rightChar)) {
                targetFreq.put(rightChar, targetFreq.get(rightChar) - 1);
                if (targetFreq.get(rightChar) >= 0) {
                    matchCount++;
                }
            }

            // 如果窗口包含了所有 t 中的字符，移动左指针缩小窗口
            while (matchCount == t.length()) {
                // 如果当前窗口长度小于 minLen，更新 minLen 和 start。
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }

                // 如果左指针指向的字符是字符串 t 中的字符，更新 targetFreq 中相应字符频率，如果频率大于0，减少匹配字符数量。
                char leftChar = s.charAt(left);
                if (targetFreq.containsKey(leftChar)) {
                    targetFreq.put(leftChar, targetFreq.get(leftChar) + 1);
                    if (targetFreq.get(leftChar) > 0) {
                        matchCount--;
                    }
                }
                left++;
            }
            right++;
        }

        // 返回最小覆盖子串，如果没有找到则返回空字符串。
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

步骤解释：

检查输入的字符串是否为空，以及字符串 s 的长度是否小于字符串 t 的长度，如果是则直接返回空字符串。
统计字符串 t 中每个字符的频率，使用哈希表 targetFreq 存储。
初始化左右指针 left 和 right，记录最小覆盖子串的起始位置和最小覆盖子串的长度，以及匹配字符数量。
使用双指针维护滑动窗口，遍历字符串 s：
如果当前字符是字符串 t 中的字符，则在 targetFreq 中相应字符频率减1，如果频率大于等于0，增加匹配字符数量。
如果窗口包含了所有 t 中的字符，移动左指针缩小窗口。
在内层循环中，不断移动左指针，收缩窗口，同时更新最小覆盖子串的起始位置和长度。
返回最小覆盖子串，如果没有找到则返回空字符串。

时间复杂度： 遍历字符串一次，时间复杂度为 O(n)。

空间复杂度： 使用了哈希表存储字符串 t 中字符的频率，空间复杂度为 O(m)，其中 m 是字符串 t 的长度。