给定两个字符串 S 和 T,求 S 中包含 T 所有字符的最短连续子字符串的长度,同时要求时间复杂度不得超过 O(n)。
输入
输入是两个字符串 S 和 T
输出
输出是一个 S 字符串的子串。
样例
标准输入 复制文本 |
S = "ADOBECODEBANC", T = "ABC" |
标准输出 复制文本 |
"BANC" |
提示
本题使用滑动窗口求解,即两个指针 l 和 r 都是从最左端向最右端移动,且 l 的位置一定在 r 的左边或重合。注意本题虽然在 for 循环里出现了一个 while 循环,但是因为 while 循环负责移 动 l 指针,且 l 只会从左到右移动一次,因此总时间复杂度仍然是 O(n)。本题使用了长度为 128 的数组来映射字符,也可以用哈希表替代;其中 chars 表示目前每个字符缺少的数量,flag 表示 每个字符是否在 T 中存在。