算法技巧 - 滑动窗口

以下题目适用

最小覆盖子串 (opens new window)

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

func minWindow(s string, t string) string { // 10 min 解决
    need, window := map[byte]int{}, map[byte]int{}
    left, right, valid, start := 0,0,0,0
    length := math.MaxInt

    // 记录满足字符串的频数
    for i:= 0; i < len(t); i++ {
        need[t[i]]++
    }

    for right < len(s) {
        c := s[right]
        right++ //扩大窗口

        window[c]++
        if window[c] == need[c]{ //相等时，说明有一个字符满足了条件
            valid++
        }


        for valid == len(need) {
            if right - left < length { // 判断一下，更新一下，最小子串的长度和起始值
                start = left
                length = right - left
            }

            d := s[left]
            left++
            if window[d] == need[d]{
                valid--
            }
            window[d]--
        }
    }

    if length == math.MaxInt{
        return ""
    } else {
        end := start + length
        return s[start:end]
    }

}

字符串的排列 (opens new window)

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

func checkInclusion(s1 string, s2 string) bool {
    need, window := map[byte]int{}, map[byte]int{}
    left, right, valid := 0,0,0

    for i:=0; i<len(s1);i++{
        need[s1[i]]++
    }

    for right < len(s2) {
        c := s2[right]
        right++
        if _, ok := need[c];ok{
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }
        
        // todo PS：由于这道题中 [left, right) 其实维护的是一个定长的窗口，窗口大小为  len(s1)。因为定长窗口每次向前滑动时只会移出一个字符，所以可以把内层的 while 改成 if，效果是一样的。
        for right - left >= len(s1) { // 判断左侧窗口是否要收缩：本题移动 left 缩小窗口的时机是窗口大小大于 len(s1) 时
            if valid == len(need) { // 当发现 valid == len(need) 时，就说明窗口中就是一个合法的排列，所以立即返回 true。
                return true
            }
            d := s2[left]
            left++
            if _, ok := need[d];ok{
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }

    return false
}

找到字符串中所有字母异位词 (opens new window)

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

func findAnagrams(s string, p string) []int {
    need, window := map[byte]int{}, map[byte]int{}
    left, right, valid := 0,0,0
    var res []int
    for i:=0;i<len(p);i++ {
        need[p[i]]++
    }
    for right < len(s) {
        c := s[right]
        right++
        if _,ok := need[c];ok {
            window[c]++
            if need[c] == window[c] {
                valid++
            }
        }

        for right - left >= len(p) {
            if valid == len(need) { // 当窗口符合条件时，把起始索引加入 res
                res = append(res, left)
            }

            d := s[left]
            left++
            if _,ok := need[d];ok {
                if need[d] == window[d] {
                    valid--
                }
                window[d]--
            }
            
        }
    }

    return res
}

无重复字符的最长子串 (opens new window)

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

func lengthOfLongestSubstring(s string) int {
    window := map[byte]int{}
    left, right, res  := 0,0,0
    for right < len(s) {
        c := s[right]
        right++
        window[c]++     
        for window[c] > 1 {
            d := s[left]
            left++
            window[d]--
        }
        res = max(res, right - left)
    }
    return res
}

func max(a,b int) int {
    if a >= b {
        return a
    }else {
        return b
    }
}

反转字符串 (opens new window)

题目描述

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须**原地 (opens new window)修改输入数组**、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

题解

func reverseString(s []byte)  {
    left := 0
    right := len(s) - 1

    for left < right{
        s[left],s[right] = s[right], s[left]
        left++
        right--
    }
}

验证回文串 (opens new window)

题目描述

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

示例 1：

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

思路

1. 所有字符转化成小写

2. 过滤掉空格和标点这类字符

3. 剩下的字符执行，两端向中心的双指针算法

题解

func isPalindrome(s string) bool {
    if s == " " {
        return true
    }

    var sgood string
    for i := 0; i < len(s); i++ {
        if isalnum(s[i]) {
            sgood += string(s[i])
        }
    }

    sgood = strings.ToLower(sgood)
    left := 0
    right := len(sgood) - 1

    for left < right {
        if sgood[left] != sgood[right] {
            return false
        }
        left++
        right--
    }

    return true
}

func isalnum(ch byte) bool {
    return (ch >= 'A' && ch <= 'Z') || (ch >= 'a' && ch <= 'z') || (ch >= '0' && ch <= '9')
}

最长回文串 (opens new window)

题目

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

题解

func longestPalindrome(s string) string {
    var res string
    for i := 0; i < len(s); i++ {
        s1 := palindrome(s,i,i) // 以 s[i] 为中心的最长回文子串
        s2 := palindrome(s,i,i + 1) // 以 s[i] 和 s[i+1] 为中心的最长回文子串
        s1L := len(s1)
        s2L := len(s2)

        if len(res) < s1L {
            res = s1
        }
        if len(res) < s2L {
            res = s2
        }
    }
    return res
}

// 在 s 中寻找以 s[l] 和 s[r] 为中心的最长回文串
// 如果输入相同的 l 和 r，就相当于寻找长度为奇数的回文串，如果输入相邻的 l 和 r，则相当于寻找长度为偶数的回文串。
func palindrome (s string, l int ,r int) string {

    for l >= 0 && r < len(s) && s[l] == s[r] {
        // 双指针，向两边展开
        l--
        r++
    }
    // 返回以 s[l] 和 s[r] 为中心的最长回文串
    return s[l+1:r]
}