本题使用 滑动窗口 + 哈希表 进行求解。
定义哈希表
need: 存储 t 中各字符的需求数量。window: 记录当前窗口内字符的出现次数。扩展窗口
left 和 right,初始时 left=0, right=0。给定字符串 s 与字符串 t,请在 s 中找出包含 t 中所有字符(含出现次数) 的最短子串并输出该子串。
若 s 中不存在这样的子串,输出空字符串 ""(不带引号)。
注:对
t中重复字符,子串中对应字符的数量必须不少于t中该字符的数量。若存在解,保证答案唯一。
st""。输入:
ADOBECODEBANC
ABC
输出:
BANC
输入:
a
a
输出:
a
输入:
a
aa
输出:
1 ≤ |s|, |t| ≤ 10^5s与t由英文字母组成