Week 5 @ 2025 算法周记【滑动窗口】

1 滑动窗口

滑动窗口

LC 76. Minimum Window Substring 最小覆盖子串

https://leetcode.com/problems/minimum-window-substring/

func minWindow(s string, t string) string {
    expect := toNumArray(t)

    window := newNumArray()
    result := ""

    left, right := 0, 0
    for right < len(s) {
        window.Add(s[right])
        right++

        for left < right && window.GreaterThanOrEqual(expect) {
            window.Remove(s[left])

            result = shorter(result, s[left:right])

            left++
        }
    }

    return result
}

type NumArray []int

func newNumArray() NumArray {
    return make(NumArray, 52)
}

func (arr NumArray) Add(c byte) {
    arr[toNum(c)]++
}

func (arr NumArray) Remove(c byte) {
    arr[toNum(c)]--
}

func (arr NumArray) GreaterThanOrEqual(another NumArray) bool {
    for i := range arr {
        if arr[i] < another[i] {
            return false
        }
    }
    return true
}

func toNumArray(s string) NumArray {
    arr := newNumArray()
    for i := range s {
        arr.Add(s[i])
    }
    return arr
}

func toNum(c byte) int {
    if c >= 'a' && c <= 'z' {
        return int(c - 'a')
    }
    if c >= 'A' && c <= 'Z' {
        return int(c - 'A') + 26
    }

    return -1
}

func shorter(base, s string) string {
    if base == "" || len(s) < len(base) {
        return s
    }
    return base
}

优化

利用统计「满足窗口条件的字符数」减少 GreaterThanOrEqual 判断的成本

func minWindow(s string, t string) string {
    expect := toNumArray(t)

    window := newNumArray()
    result := ""

    valid := 0
    expectValid := 0
    for _, c := range expect {
        if c > 0 {
            expectValid++
        }
    }

    left, right := 0, 0
    for right < len(s) {
        rx := toNum(s[right])
        right++

        if expect[rx] > 0 {
            window[rx]++
            if window[rx] == expect[rx] {
                valid++
            }
        }

        for left < right && valid == expectValid {
            lx := toNum(s[left])
            if expect[lx] > 0 {
                if window[lx] == expect[lx] {
                    valid--
                }

                window[lx]--
            }
            
            result = shorter(result, s[left:right])

            left++
        }
    }

    return result
}

type NumArray []int

func newNumArray() NumArray {
    return make(NumArray, 52)
}

func toNumArray(s string) NumArray {
    arr := newNumArray()
    for i := range s {
        arr[toNum(s[i])]++
    }
    return arr
}

func toNum(c byte) int {
    if c >= 'a' && c <= 'z' {
        return int(c - 'a')
    }
    if c >= 'A' && c <= 'Z' {
        return int(c - 'A') + 26
    }

    return -1
}

func shorter(base, s string) string {
    if base == "" || len(s) < len(base) {
        return s
    }
    return base
}

LC 567. Permutation in String 字符串的排列

https://leetcode.com/problems/permutation-in-string/

func checkInclusion(s1 string, s2 string) bool {
    expect := toNumberMap(s1)
    window := newNumberMap()

    valid := 0
    expectValid := 0
    for _, c := range expect {
        if c > 0 {
            expectValid++
        }
    }

    left, right := 0, 0

    for right < len(s2) {
        rx := toNumber(s2[right])
        if expect[rx] > 0 {
            window[rx] ++

            if expect[rx] == window[rx] {
                valid++
            }
        }
        right++

        for left < right && valid == expectValid {
            lx := toNumber(s2[left])
            if expect[lx] > 0 {
                if expect[lx] == window[lx] {
                    valid--
                }

                window[lx]--
            }

            if right-left == len(s1) {
                return true
            }


            left++
        }
    }

    return false
}

type NumberMap []int

func newNumberMap() NumberMap {
    return make(NumberMap, 26)
}

func toNumberMap(s string) NumberMap {
    m := newNumberMap()

    for i := range s {
        m[toNumber(s[i])]++
    }

    return m
}

func toNumber(c byte) int {
    return int(c - 'a')
}

思路二：定长窗口

LC 438. Find All Anagrams in a String 找到字符串中所有字母异位词

https://leetcode.com/problems/find-all-anagrams-in-a-string/

LC 3. Longest Substring Without Repeating Characters 无重复字符的最长子串

https://leetcode.com/problems/longest-substring-without-repeating-characters/

简化判断逻辑

（时间复杂度一样，但是似乎总执行时间没有上面引入 dup 做判断好 7ms vs 0ms - 当然不确定是否是 leetcode 的原因）