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

• 题目考察的知识点 : 滑动窗口
• 题目解答方法的文字分析：

1. 使用 Counter 统计 t 中每个字符的需求量
2. need 记录还需匹配的字符总数,need==0 表示匹配完成
3. 使用左右指针 left, right 定义滑动窗口
4. right 右移扩大窗口,并更新 need 和 cnt
5. 当 need==0 时,开始左移 left 缩小窗口
6. 每次更新最小窗口大小,并记录起始位置
7. 最终返回最小覆盖子串

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param s string字符串 
# @param t string字符串 
# @return string字符串
#
import collections
class Solution:
    def minWindow(self , s: str, t: str) -> str:
        if len(t) > len(s):
            return ''        
        
        cnt = collections.Counter(t)    # 哈希表：记录需要匹配到的各个元素的数目
        need = len(t)                   # 记录需要匹配到的字符总数【need=0表示匹配到了】
        
        n = len(s)
        start, end = 0, -1          # 记录目标子串s[start, end]的起始和结尾
        min_len = n + 1            
        left = right = 0            # 滑动窗口的左右边界
        
        for right in range(n):
            
            # 窗口右边界右移一位
            ch = s[right]               # 窗口中新加入的字符
            if ch in cnt:               # 新加入的字符位于t中
                if cnt[ch] > 0:         # 对当前字符ch还有需求
                    need -= 1           # 此时新加入窗口中的ch对need有影响
                cnt[ch] -= 1
            
            # 窗口左边界持续右移
            while need == 0:            # need=0，当前窗口完全覆盖了t
                if right - left + 1 < min_len:      # 出现了更短的子串
                    min_len = right - left + 1
                    start, end = left, right
                
                ch = s[left]            # 窗口中要滑出的字符
                if ch in cnt:           # 刚滑出的字符位于t中
                    if cnt[ch] >= 0:    
                        need += 1       # 此时滑出窗口的ch会对need有影响
                    cnt[ch] += 1
                left += 1               # 窗口左边界+1
        
        return s[start: end+1]