java 最小子串覆盖

Java 中求最小子串覆盖可以使用滑动窗口算法。

算法步骤：

1. 统计 t 中每个字符出现的次数；
2. 用两个指针 left 和 right 表示滑动窗口的左右边界，初始时均指向字符串的第一个字符；
3. right 向右移动，直到包含了 t 中所有的字符；
4. 记录当前窗口的大小和位置；
5. left 向右移动，缩小窗口，直到不再包含 t 中所有字符；
6. 重复 3 - 5 步骤，直到 right 达到字符串的末尾。

Java 代码实现：

public String minWindow(String s, String t) {
    if (s == null || t == null || s.length() == 0 || t.length() == 0) {
        return "";
    }

    // 统计 t 中每个字符出现的次数
    int[] count = new int[128];
    for (char c : t.toCharArray()) {
        count[c]++;
    }

    // 初始化 left、right 和 minLen
    int left = 0, right = 0, minLen = Integer.MAX_VALUE;
    String result = "";

    // 窗口中 t 的字符数量
    int tCount = t.length();

    // 移动 right 指针
    while (right < s.length()) {
        char c = s.charAt(right);
        if (count[c] > 0) {
            tCount--;
        }
        count[c]--;
        right++;

        // 如果包含了 t 中所有字符
        while (tCount == 0) {
            if (right - left < minLen) {
                minLen = right - left;
                result = s.substring(left, right);
            }

            char c2 = s.charAt(left);
            if (count[c2] == 0) {
                tCount++;
            }
            count[c2]++;
            left++;
        }
    }

    return result;
}