题解 | #牛群名字覆盖# 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
        Map<Character, Integer> m = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            m.put(t.charAt(i), m.getOrDefault(t.charAt(i), 0) - 1);
        }

        int slow = 0, fast = 0;
        int left = -1, right = -1;
        int cnt = s.length() + 1;

        while (fast < s.length()) {
            char c = s.charAt(fast);
            if (m.containsKey(c)) {
                m.put(c, m.get(c) + 1);
            }
            while (check(m)) {
                if (cnt > fast - slow + 1) {
                    cnt = fast - slow + 1;
                    left = slow;
                    right = fast;
                }
                char ch = s.charAt(slow);
                if (m.containsKey(ch)) {
                    m.put(ch, m.get(ch) - 1);
                }
                slow++;
            }
            fast++;
        }
        if (left == -1) {
            return "";
        }
        return s.substring(left, right + 1);
    }

    private boolean check(Map<Character, Integer> m) {
        for (Integer value : m.values()) {
            if (value < 0) {
                return false;
            }
        }
        return true;
    }
}

程语言是Java。

该题考察的知识点包括使用滑动窗口技巧找到字符串中包含指定字符集合的最小窗口子串。

代码的文字解释：通过滑动窗口来找到字符串s中包含指定字符串t的最小窗口子串。

使用HashMap统计字符串t中每个字符出现的次数，使用负数表示需要的字符个数。

通过滑动窗口遍历字符串s，在循环中进行以下操作：

• 将当前字符对应的计数增加1。
• 在while循环中，检查窗口内的子串是否包含了字符串t中的所有字符。如果是，则从窗口的左侧收缩，找到包含t所有字符的最小窗口子串。
• 将当前窗口内的子串与已知的最小窗口子串进行比较，更新最小窗口子串。