题解 | #牛群名字覆盖#

知识点

滑动窗口

解题思路

我们需要统计目标字母表t中每个字母出现的频率。然后，我们使用两个指针left和right来维护一个滑动窗口。

具体步骤如下：

1. 初始化指针left和right为字符串s的起始位置。
2. 移动指针right，扩展窗口，直到窗口中包含了所有目标字母表t中的字母。
3. 记录当前窗口的长度和起始位置。
4. 移动指针left，缩小窗口，直到窗口无法再排除目标字母表t中的字母。
5. 重复步骤2-4，直到指针right到达字符串s的末尾。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param t string字符串
     * @return string字符串
     */
    public String minWindow (String s, String t) {
        // write code here
        int[] targetFreq = new
        int[128]; // 用于统计目标字母表t中每个字母的频率
        for (char c : t.toCharArray()) {
            targetFreq[c]++;
        }

        int[] windowFreq = new int[128]; // 用于统计窗口中每个字母的频率
        int left = 0; // 窗口的左指针
        int right = 0; // 窗口的右指针
        int minLength = Integer.MAX_VALUE; // 最小窗口的长度
        int start = 0; // 最小窗口的起始位置

        int count = t.length(); // 窗口中包含的目标字母的总数

        while (right < s.length()) {
            char c = s.charAt(right);
            windowFreq[c]++;

            if (windowFreq[c] <= targetFreq[c]) {
                count--;
            }

            while (count == 0) {
                // 更新最小窗口的起始位置和长度
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    start = left;
                }

                char leftChar = s.charAt(left);
                windowFreq[leftChar]--;
                if (windowFreq[leftChar] < targetFreq[leftChar]) {
                    count++;
                }

                left++; // 缩小窗口
            }

            right++; // 扩展窗口
        }

        if (minLength == Integer.MAX_VALUE) {
            return "";
        }

        return s.substring(start, start + minLength);
    }
}