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 i, j, l, r, slen = s.length(), tlen = t.length(), remain;
        String res = "";

        if (slen >= tlen) {
            Map<Character, Integer> mp = new HashMap<>();
            for (i = 0; i < tlen; i++) {
                char c = t.charAt(i);
                mp.put(c, mp.getOrDefault(c, 0) + 1);
            }

            for (i = 0, j = 0, l = -1, r = -1, remain = tlen; j < slen; j++) {
                char c = s.charAt(j);
                if (mp.containsKey(c)) {
                    mp.put(c, mp.get(c) - 1);
                    if (mp.get(c) >= 0)
                        remain--;
                    if (remain == 0) {
                        while (!mp.containsKey(s.charAt(i)) || mp.get(s.charAt(i)) < 0) {
                            if (mp.containsKey(s.charAt(i)))
                                mp.put(s.charAt(i), mp.get(s.charAt(i)) + 1);
                            i++;
                        }
                        if (l == -1 && r == -1 || j - i < r - l) {
                            l = i;
                            r = j;
                        }
                        mp.put(s.charAt(i), mp.get(s.charAt(i)) + 1);
                        remain++;
                        i++;
                    }
                }
            }
            if (l != -1 && r != -1)
                res = s.substring(l, r + 1);
        }

        return res;
    }
}

该代码使用的编程语言是Java。

此题考察的知识点是滑动窗口算法

这段代码实现了一个函数 minWindow，该函数接受两个字符串作为参数：s 和 t。它的目标是在字符串 s 中找到包含字符串 t 所有字符的最小窗口，并返回该窗口对应的子串。

代码中的主要逻辑如下：

1. 判断字符串 s 的长度是否大于等于字符串 t 的长度。如果不满足这个条件，则直接返回空字符串。
2. 创建一个 HashMap 对象 mp，用来存储字符串 t 中每个字符出现的频率。
3. 遍历字符串 t，更新 mp 中每个字符的频率。
4. 初始化双指针 i 和 j 分别指向字符串 s 的起始位置，并设置初始窗口的左边界 l 和右边界 r 为 -1。设置变量 remain 表示还需要匹配的字符个数，并将其初始化为字符串 t 的长度。
5. 使用一个循环遍历字符串 s，从左到右依次移动右指针 j。在每次移动右指针后，更新 mp 中相应字符的频率，并根据频率判断是否匹配到了一个字符。
6. 当窗口中包含了全部需要匹配的字符时，开始移动左指针 i 来尝试缩小窗口的大小。具体操作是，当遇到一个不在字符串 t 中的字符或者某个字符在窗口中的出现频率超过了在 t 中的出现频率时，将左指针右移，并更新 mp 中对应字符的频率。
7. 当不能再移动左指针 i 时，表示窗口已经缩小到最小，并且包含了字符串 t 的所有字符。此时，如果窗口的大小比之前找到的最小窗口还要小，就更新最小窗口的起始位置和终止位置。
8. 根据最小窗口的起始位置和终止位置，在原字符串 s 中提取出最小窗口对应的子串，并将其赋值给变量 res。
9. 如果最小窗口的起始位置和终止位置都不是 -1，则将子串赋值给变量 res。最终，返回 res。