2021-08-30：给定两个字符串str1和str2，在str1中寻找一个最短子串，能包含str2的所有字符，字符顺序无所谓，str1的这个最短子串也可以包含多余的字符。返回这个最短包含子串。
福大大 答案2021-08-30：
滑动+哈希。对str2欠账表哈希，对str1滑动窗口。
时间复杂度：O(N)。
空间复杂度：O(1)。哈希是256的固定长度。
代码用golang编写。代码如下：
package main
import (
"fmt"
"math"
)
func main() {
s1 := "abcxa"
s2 := "aabc"
ret := minLength(s1, s2)
fmt.Println(ret)
}
func minLength(s1 string, s2 string) int {
if len(s1) < len(s2) {
return math.MaxInt64
}
map0 := make([]int, 256) // map[37] = 4 37 4次
for i := 0; i != len(s2); i++ {
map0[s2[i]]++
}
all := len(s2)
// [L,R-1] R
// [L,R) -> [0,0)
L := 0
R := 0
minLen := math.MaxInt64
for R != len(s1) {
map0[s1[R]]--
if map0[s1[R]] >= 0 {
all--
}
if all == 0 { // 还完了
for map0[s1[L]] < 0 {
map0[s1[L]]++
L++
}
// [L..R]
minLen = getMin(minLen, R-L+1)
all++
map0[s1[L]]++
L++
}
R++
}
if minLen == math.MaxInt64 {
return 0
} else {
return minLen
}
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}
执行结果如下：
左神java代码
