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。

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

滑动窗口算法是一种用于解决字符串或数组相关问题的常用技巧。它通过维护一个窗口，来在给定的字符串或数组上执行操作。具体而言，在解决子串、子数组或满足特定条件的连续序列等问题时，滑动窗口算法可以高效地解决。

代码的文字解释如下：

1. 遍历字符串t，将每个字符及其出现次数添加到need中。
2. 初始化左指针left、右指针right为0，初始化计数器valid为0，初始化起始位置start为0，长度len为无穷大
3. 进入while循环，右指针向右移动，直到遍历完字符串s：获取当前字符c=s[right]。如果字符c在需求字符集need中，则更新滑动窗口窗口中字符c的出现次数并更新计数器valid。进入内层while循环，判断当前窗口中的子串是否满足需求，即valid是否等于t的长度：如果满足需求，则更新最小窗口的起始位置start和长度len。获取左指针对应的字符d=s[left]。如果字符d在需求字符集need中，则更新滑动窗口中字符d的出现次数并更新计数器valid。左指针右移。
4. 返回结果，如果长度len仍为无穷大，则返回空字符串""；否则，根据起始位置start和长度len截取字符串s得到最小窗口子串。