滑动窗口模板

一句话说明

滑动窗口是双指针的一种应用，通过维护一个窗口来优化子串/子数组问题。

💻 模板代码

适用场景

窗口类型	适用场景	特点
固定窗口	长度固定的子数组	简单，直接滑动
最长窗口	最长无重复、最长满足条件	扩大为主，违规时收缩
最短窗口	最小覆盖、最短满足条件	满足时收缩，求最小
计数窗口	统计子串/子数组数量	利用”最多k个”的性质

💡 解题步骤

1. 初始化：left = 0, window = {}, result
2. 扩大窗口：right右移，更新window
3. 收缩窗口：while条件满足时，left右移
4. 更新结果：在合适的时机更新答案

🎯 经典题目

题目	LeetCode	窗口类型
无重复字符的最长子串	3	最长窗口
最小覆盖子串	76	最短窗口
字符串的排列	567	固定目标
找到字符串中所有字母异位词	438	固定目标
长度最小的子数组	209	最短窗口

Go 代码

// 无重复字符的最长子串
func lengthOfLongestSubstring(s string) int {
    left := 0
    window := make(map[byte]int)
    maxLen := 0
 
    for right := 0; right < len(s); right++ {
        c := s[right]
        window[c]++
 
        for window[c] > 1 {
            d := s[left]
            window[d]--
            left++
        }
 
        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }
 
    return maxLen
}
 
// 最小覆盖子串
func minWindow(s string, t string) string {
    if len(s) == 0 || len(t) == 0 {
        return ""
    }
 
    need := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        need[t[i]]++
    }
 
    window := make(map[byte]int)
    left, valid := 0, 0
    minLen, start := len(s)+1, 0
 
    for right := 0; right < len(s); right++ {
        c := s[right]
 
        if _, ok := need[c]; ok {
            window[c]++
            if window[c] == need[c] {
                valid++
            }
        }
 
        for valid == len(need) {
            if right-left+1 < minLen {
                minLen = right - left + 1
                start = left
            }
 
            d := s[left]
            left++
 
            if _, ok := need[d]; ok {
                if window[d] == need[d] {
                    valid--
                }
                window[d]--
            }
        }
    }
 
    if minLen == len(s)+1 {
        return ""
    }
    return s[start : start+minLen]
}

---

返回：算法模板