题解 | #寻找完成任务所需最短时间#

知识点

哈希，双指针

解题思路

首先，统计字符串t中每个字符出现的次数，保存在map中。

然后，使用两个指针left和right构建一个滑动窗口，初始时窗口为空。right向右移动扩展窗口，直到窗口包含了t中的所有字符。此时，计算窗口的长度，并将left向右移动缩小窗口，直到窗口不再包含t的所有字符。在整个过程中，不断更新最小子串的长度和起始位置。

最后，返回最小子串，如果不存在满足条件的子串，则返回空字符串""。

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
        // 记录t中每个字符的出现次数
        Map<Character, Integer> targetChars = new HashMap<>();
        for (char c : t.toCharArray()) {
            targetChars.put(c, targetChars.getOrDefault(c, 0) + 1);
        }

        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);
            if (targetChars.containsKey(c)) {
                if(targetChars.get(c) > 0){
                    count--;
                }
                targetChars.put(c, targetChars.get(c) - 1);
            }
            right++;

            while (count == 0) {
                if (right - left < minLength) {
                    minLength = right - left;
                    start = left;
                }

                char cLeft = s.charAt(left);
                if (targetChars.containsKey(cLeft)) {
                    targetChars.put(cLeft, targetChars.get(cLeft) + 1);
                    if (targetChars.get(cLeft) > 0) {
                        count++;
                    }
                }

                left++;
            }
        }

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