题解 | #寻找完成任务所需最短时间# 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> need = new HashMap<>();
        Map<Character, Integer> window = new HashMap<>();
        for (char c : t.toCharArray()) {
            need.put(c, need.getOrDefault(c, 0) + 1);
        }

        int left = 0, right = 0;
        int valid = 0;
        int start = 0, len = Integer.MAX_VALUE;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                if (window.get(c) <= need.get(c)) {
                    valid++;
                }
            }

            while (valid == t.length()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }

                char d = s.charAt(left);
                left++;
                if (need.containsKey(d)) {
                    if (window.get(d) <= need.get(d)) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }

        return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
    }
}

编程语言是Java。

该题考察的知识点是滑动窗口和哈希表。

代码的文字解释：

• minWindow方法接受两个字符串S和T作为参数，并返回一个字符串。
• 创建两个哈希表，need用于记录字符串T中每个字符的出现次数，window用于记录当前窗口中每个字符的出现次数。
• 使用双指针left和right表示当前窗口的左右边界，valid表示窗口中满足要求的字符数量。
• 创建变量start和len分别用于记录最小覆盖子串的起始位置和长度，初始值设置为最大整数。
• 进入循环，每次将右指针向右移动一位，并更新window中对应字符的出现次数。如果当前字符属于字符串T中的字符，则将valid加一。
• 当窗口中满足要求的字符数量等于字符串T的长度时，进入内层循环。在内层循环中，判断当前窗口是否是最小覆盖子串，如果是，则更新start和len的值。
• 将左指针向右移动一位，并更新window中对应字符的出现次数。如果移除的字符属于字符串T中的字符，并且在移除之前该字符在窗口中的数量小于等于在字符串T中的数量，则将valid减一。
• 最后返回最小覆盖子串，如果没有找到则返回空字符串。