| Table of Contents | ||
|---|---|---|
|
滑动窗口
模板
| Code Block |
|---|
int left = 0, right = 0;
while (right < nums.size()) {
// 增大窗口
window.addLast(nums[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.removeFirst(nums[left]);
left++;
}
} |
| Code Block | ||
|---|---|---|
| ||
// 滑动窗口算法伪码框架
func slidingWindow(s string) {
// 用合适的数据结构记录窗口中的数据，根据具体场景变通
// 比如说，我想记录窗口中元素出现的次数，就用 map
// 如果我想记录窗口中的元素和，就可以只用一个 int
var window = ...
left, right := 0, 0 // 把索引左闭右开区间 [left, right) 称为一个「窗口」
for right < len(s) {
// c 是将移入窗口的字符
c := rune(s[right])
window[c]++
// 增大窗口
right++
// 进行窗口内数据的一系列更新
...
// *** debug 输出的位置 ***
// 注意在最终的解法代码中不要 print
// 因为 IO 操作很耗时，可能导致超时
fmt.Println("window: [",left,", ",right,")")
// ***********************
// 判断左侧窗口是否要收缩
for left < right && window needs shrink { //replace "window needs shrink" with actual condition
// d 是将移出窗口的字符
d := rune(s[left])
window[d]--
// 缩小窗口
left++
// 进行窗口内数据的一系列更新
...
}
}
} |
LC 76. Minimum Window Substring 最小覆盖子串
https://leetcode.com/problems/minimum-window-substring/
| Code Block | ||
|---|---|---|
| ||
func minWindow(s string, t string) string {
T := toWindow(t)
initialResult := "x" + s
result := initialResult
var window [52]int
l, r := 0, 0
for r < len(s) {
windowAdd(&window, s[r])
r++
// fmt.Println("window: [",l,", ",r,")", s[l:r], "->", result)
for l < r && windowContains(window, T) {
if r - l < len(result) {
result = s[l:r]
}
windowRemove(&window, s[l])
l++
}
}
if result == initialResult {
return ""
}
return result
}
func toIndex(c byte) int {
if c >= 'A' && c <= 'Z' {
return int(c - 'A')
} else if c >= 'a' && c <= 'z' {
return 26 + int(c - 'a')
} else {
panic("Invalid character")
}
}
func toWindow(s string) (w [52]int) {
for _, r := range s {
w[toIndex(byte(r))]++
}
return
}
func windowAdd(window *[52]int, c byte) {
(*window)[toIndex(c)]++
}
func windowRemove(window *[52]int, c byte) {
(*window)[toIndex(c)]--
}
func windowContains(window1, window2 [52]int) bool { // window1 contains all window2
for i := range window1 {
if window1[i] < window2[i] {
return false
}
}
return true
} |
优化
| Code Block | ||
|---|---|---|
| ||
func minWindow(s string, t string) string {
need := toWindow(t)
valid := 0
expectValid := 0
for _, v := range need {
if v > 0 {
expectValid++
}
}
start, end := 0, math.MaxInt
var window [52]int
l, r := 0, 0
for r < len(s) {
ri := toIndex(s[r])
if need[ri] > 0 {
window[ri]++
if window[ri] == need[ri] {
valid++
}
}
r++
for l < r && valid == expectValid {
if r - l < end - start {
start = l
end = r
}
li := toIndex(s[l])
if need[li] > 0 {
if window[li] == need[li] {
valid--
}
window[li]--
}
l++
}
}
if end == math.MaxInt {
return ""
}
return s[start:end]
}
func toIndex(c byte) int {
if c >= 'A' && c <= 'Z' {
return int(c - 'A')
} else if c >= 'a' && c <= 'z' {
return 26 + int(c - 'a')
} else {
panic("Invalid character")
}
}
func toWindow(s string) (w [52]int) {
for _, r := range s {
w[toIndex(byte(r))]++
}
return
}
|
优化点：
利用 valid + expectValid 优化 windowContains 的判断
原来的 windowContains 每次都要遍历 window 和 need，优化后不需要了
valid 是「need 中有的字符在 window 中也有至少相同数量的字符数」（即 s 已经满足了 t 要求的字符数）
通过操作 valid 可更好的利用窗口的特性，降低比较成本
利用 [start, end) 替换 result - 避免每次创建 string（虽然按照 Go 的实现应该成本不大，不一定很有效的优化，但至少是个差异点、至少降低了内存分配）
（其实不算个优化，是个备注而已）网上的答案大都用了 map，但我觉得既然已经限定了字符只能是 a-zA-z，所以用 array 应该比 map 要效率高
LC 567. Permutation in String 字符串的排列
https://leetcode.com/problems/permutation-in-string/
| Code Block | ||
|---|---|---|
| ||
func checkInclusion(s1 string, s2 string) bool {
expect := toMap(s1)
var window [26]int
l, r := 0, 0
for r < len(s2) {
window[idx(s2[r])]++
r++
for l < r && matchExpect(&window, &expect) {
if r - l == len(s1) {
return true
}
window[idx(s2[l])]--
l++
}
}
return false
}
func idx(c byte) int {
return int(c - 'a')
}
func toMap(s string) (m [26]int) {
for _, c := range s {
m[idx(byte(c))]++
}
return
}
func matchExpect(window, expect *[26]int) bool {
for i := 0; i < 26; i++ {
if (*window)[i] < (*expect)[i] {
return false
}
}
return true
} |
利用和上一题（LC.76）类似的优化，另一解法
| Code Block | ||
|---|---|---|
| ||
func checkInclusion(s1 string, s2 string) bool {
expect := toMap(s1)
var window [26]int
valid := 0
expectValid := 0
for _, v := range expect {
if v > 0 {
expectValid++
}
}
l, r := 0, 0
for r < len(s2) {
ri := idx(s2[r])
if expect[ri] > 0 {
window[ri]++
if expect[ri] == window[ri] {
valid++
}
}
r++
for l < r && valid == expectValid {
if r - l == len(s1) {
return true
}
li := idx(s2[l])
if expect[li] > 0 {
if expect[li] == window[li] {
valid--
}
window[li]--
}
l++
}
}
return false
}
func idx(c byte) int {
return int(c - 'a')
}
func toMap(s string) (m [26]int) {
for _, c := range s {
m[idx(byte(c))]++
}
return
} |
还有另一种思路 —— 条件不是 valid，而是窗口定长
| Code Block | ||
|---|---|---|
| ||
func checkInclusion(s1 string, s2 string) bool {
expect := toMap(s1)
var window [26]int
valid := 0
expectValid := 0
for _, v := range expect {
if v > 0 {
expectValid++
}
}
l, r := 0, 0
for r < len(s2) {
ri := idx(s2[r])
if expect[ri] > 0 {
window[ri]++
if expect[ri] == window[ri] {
valid++
}
}
r++
if r - l >= len(s1) { // <- 这里换成了 if
if valid == expectValid {
return true
}
li := idx(s2[l])
if expect[li] > 0 {
if expect[li] == window[li] {
valid--
}
window[li]--
}
l++
}
}
return false
}
func idx(c byte) int {
return int(c - 'a')
}
func toMap(s string) (m [26]int) {
for _, c := range s {
m[idx(byte(c))]++
}
return
} |
注意判断窗口定长的地方换成了 if —— 其实 for 也是可以的，但因为只会收缩一次窗口所以 if 也 OK —— 甚至可以判断成 if r - l == len(s1) 因为只会在窗口长度等于 len(s1) 时触发一次窗口收缩
LC 438. Find All Anagrams in a String 找到字符串中所有字母异位词
https://leetcode.com/problems/find-all-anagrams-in-a-string/
| Code Block | ||
|---|---|---|
| ||
func findAnagrams(s string, p string) (result []int) {
expect := toMap(p)
var window [26]int
valid := 0
expectValid := 0
for _, v := range expect {
if v > 0 {
expectValid++
}
}
l, r := 0, 0
for r < len(s) {
ri := idx(s[r])
if expect[ri] > 0 {
window[ri]++
if expect[ri] == window[ri] {
valid++
}
}
r++
if r - l >= len(p) {
if valid == expectValid {
result = append(result, l)
}
li := idx(s[l])
if expect[li] > 0 {
if expect[li] == window[li] {
valid--
}
window[li]--
}
l++
}
}
return
}
func idx(c byte) int {
return int(c - 'a')
}
func toMap(s string) (m [26]int) {
for _, c := range s {
m[idx(byte(c))]++
}
return
} |
与上一题几乎一样 —— 只是将找到时返回改成了找到所有结果后一起返回
多解：一直在用 []int 代替 map，本题再搞个用 map 的解法
| Code Block | ||
|---|---|---|
| ||
func findAnagrams(s string, p string) (result []int) {
expect := make(map[byte]int, len(p))
for _, c := range p {
expect[byte(c)]++
}
window := make(map[byte]int, len(p))
valid := 0
l, r := 0, 0
for r < len(s) {
if c := s[r]; expect[c] > 0 {
window[c]++
if expect[c] == window[c] {
valid++
}
}
r++
for r - l == len(p) {
if valid == len(expect) {
result = append(result, l)
}
if c := s[l]; expect[c] > 0 {
if expect[c] == window[c] {
valid--
}
window[c]--
}
l++
}
}
return
} |
（虽然时间复杂度和用 [26]int 一样，但用 map 算是个负优化 —— 可以从 LC 的实际执行时间看出来，整整慢了十倍（1ms → 10ms））
LC 3. Longest Substring Without Repeating Characters 无重复字符的最长子串
https://leetcode.com/problems/longest-substring-without-repeating-characters/
| Code Block | ||
|---|---|---|
| ||
func lengthOfLongestSubstring(s string) int {
window := make(map[byte]int, 128)
dup := 0
maxLength := 0
l, r := 0, 0
for r < len(s) {
c := s[r]
window[c]++
if window[c] > 1 {
dup++
}
r++
for l < r && dup > 0 {
c := s[l]
if window[c] > 1 {
dup--
}
window[c]--
l++
}
maxLength = max(maxLength, r-l)
}
return maxLength
} |
注：
dup 存储重复值 —— 其实用不到，重复了直接收缩窗口就行（下面做优化）
window 因为有各种可能的值，因此没法用
[]int优化 —— 其实也有，因为题目限定在了 ASCII 以内 —— 为了简化，采用 map 但是初始化长度为 128
优化 - 不用 dup
| Code Block | ||
|---|---|---|
| ||
func lengthOfLongestSubstring(s string) int {
window := make(map[byte]int, 128)
maxLength := 0
l, r := 0, 0
for r < len(s) {
c := s[r]
window[c]++
r++
for l < r && window[c] > 1 {
window[s[l]]--
l++
}
maxLength = max(maxLength, r-l)
}
return maxLength
} |
进一步优化 - 不用 map
| Code Block | ||
|---|---|---|
| ||
func lengthOfLongestSubstring(s string) int {
window := [128]int{} // <- 其实只改了这里😂 剩下啥也没变
maxLength := 0
l, r := 0, 0
for r < len(s) {
c := s[r]
window[c]++
r++
for l < r && window[c] > 1 {
window[s[l]]--
l++
}
maxLength = max(maxLength, r-l)
}
return maxLength
} |
使用切片果然比 map 快！！从 8ms 直接降低到 0ms 。。