题目链接：https://leetcode.cn/problems/minimum-window-substring/
思路
方法：滑动窗口
1.我们用两个map存取，mpt存t字符串中的每个字符的个数，cnt用来存当前子串 s[l:r] 中每个字符个数。
2.用check()函数判断当前s[l:r]中是否可以覆盖p字符串。
3.滑动窗口一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。l，r截取s中的子串，每次r++的时候用check()匹配，check成功匹配，收缩窗口移动 l 找到s[l:r]中最小覆盖p的子串长度，并把当前的l，r赋值给ansL和ansR。
4.可能s串中不存在p的子串，这个时候我们只要判断ansL是否被改变，ansL和ansR默认初始为-1。
代码示例
func minWindow(s string, t string) string { cnt, mpt := map[byte]int{}, map[byte]int{} //统计t中每个字符个数 for i := range t{ mpt[t[i]]++ } //截取子串的范围 ansL, ansR := -1, -1 //判断当前s[l:r]中是否可以覆盖p字符串 check := func() bool{ for k, v := range mpt{ if cnt[k] < v{ return false } } return true } sLen := len(s) len := math.MaxInt32 for l, r := 0, 0; r < sLen; r++ { if r < sLen && mpt[s[r]] > 0 { cnt[s[r]]++ } //check匹配当前s[l:r]是否覆盖p for check() && l <= r { //对比最小子串长度 if r - l + 1 < len { len = r - l + 1 ansL, ansR = l, l + len } if _, ok := mpt[s[l]]; ok { cnt[s[l]] -= 1 } l++ } } if ansL == -1{ return "" } return s[ansL:ansR] }
复杂度分析
- 时间复杂度：最坏情况下左右指针对 s 的每个元素各遍历一遍，哈希表中对 s 中的每个元素各插入、删除一次，对 t 中的元素各插入一次。每次检查是否可行会遍历整个 t 的哈希表，哈希表的大小与字符集的大小有关，设字符集大小为 CC，则渐进时间复杂度为 O(C⋅∣s∣+∣t∣)。
- 空间复杂度：这里用了两张哈希表作为辅助空间，每张哈希表最多不会存放超过字符集大小的键值对，我们设字符集大小为 C ，则渐进空间复杂度为 O©。
代码优化
- 在s[l:r]里面找到最小覆盖p字符串的子串，我们通过每次check来匹配是否可以覆盖，浪费了许多时间。
- 我们可以改变思路，我们只要第一次通过check匹配是否存在p的字符串子串即可，我们移动l的位置，并且判断cnt[s[l]] - 1是否还能大于等于mpt[s[l]]的字符个数即可。
func minWindow(s string, t string) string { cnt, mpt := map[byte]int{}, map[byte]int{} //统计t中每个字符个数 for i := range t{ mpt[t[i]]++ } //截取子串的范围 ansL, ansR := -1, -1 //判断当前s[l:r]中是否可以覆盖p字符串 check := func() bool{ for k, v := range mpt{ if cnt[k] < v{ return false } } return true } sLen := len(s) len := math.MaxInt32 for l, r := 0, 0; r < sLen; r++ { if r < sLen && mpt[s[r]] > 0 { cnt[s[r]]++ } //只需一次用check匹配当前s[l:r]是否覆盖p if check(){ for l <= r { if r - l + 1 < len { len = r - l + 1 ansL, ansR = l, l + len } if _, ok := mpt[s[l]]; ok { //判断当前去掉一个s[l]是否还能匹配覆盖mpt[s[l]]的个数 if cnt[s[l]] - 1 < mpt[s[l]]{ break } cnt[s[l]] -= 1 } l++ } } } if ansL == -1{ return "" } return s[ansL:ansR] }
- 时间复杂度：O(C⋅∣s∣) 字符集大小为 C
- 空间复杂度：O© 字符集大小为 C
