题目描述（困难难度）

给两个字符串，S 和 T，在 S 中找出包含 T 中所有字母的最短字符串，不考虑顺序。

解法一 滑动窗口

没有想出来，直接看来了，这里总结一下。

用双指针 left 和 right 表示一个窗口。

思想有了，其实这里需要解决的问题只有一个，怎么来判断当前窗口包含了所有字母。

时间复杂度：O（nm），n 是 S 的长度，match 函数消耗 O（m）。

空间复杂度：O（m），m 是 T 的长度。

参考这里，由于字符串中只有字母，我们其实可以不用 hashmap，可以直接用一个 int 数组，字母的 ascii 码值作为下标，保存每个字母的次数。

此外，判断当前窗口是否含有所有字母，我们除了可以判断所有字母的次数是否小于等于 0，还可以用一个计数变量 count，把 count 初始化为 t 的长度，然后每次找到一个满足条件的字母，count 就减 1，如果 count 等于了 0，就代表包含了所有字母。这样的话，可以把之前的 match(map) 优化到 O（1）。

总

添加好友一起进步~

如果觉得有帮助的话，可以点击 给一个 star 哦 ^^

如果想系统的学习数据结构和算法，强烈推荐一个我之前学过的课程，可以点击 这里 查看详情