滑动窗口

本章目标：掌握定长与不定长滑动窗口模板，能解决子串/子数组的最值问题。

你将学到

• 定长窗口与不定长窗口的区别
• 最大/最小覆盖子串模板
• 无重复字符的最长子串
• 窗口内嵌哈希/计数
• 找所有字母异位词

1. 概念

滑动窗口是双指针的进阶应用。维护一个窗口 [left, right]，通过扩张 right 和收缩 left 来寻找满足条件的子数组/子串。

核心思想：当窗口满足条件时尝试收缩左边界以找更优解，当窗口不满足条件时扩张右边界。

滑动窗口适用于以下场景：

• 求满足条件的最大/最小连续子数组
• 字符串匹配（找包含某字符集的子串）
• 固定窗口大小的问题（如平均值、最大值）

2. 核心模板

不定长滑动窗口（求最小窗口）

// 模板：求满足条件的最小窗口
func minWindow(_ s: String, _ t: String) -> String {
    let sArr = Array(s)
    var need: [Character: Int] = [:]
    for ch in t { need[ch, default: 0] += 1 }
    var window: [Character: Int] = [:]
    var left = 0, right = 0
    var valid = 0  // 已满足的字符种类数
    var start = 0, minLen = Int.max

    while right < sArr.count {
        let c = sArr[right]
        right += 1
        // 扩张窗口
        if need[c] != nil {
            window[c, default: 0] += 1
            if window[c] == need[c] { valid += 1 }
        }
        // 收缩窗口
        while valid == need.count {
            if right - left < minLen {
                start = left
                minLen = right - left
            }
            let d = sArr[left]
            left += 1
            if need[d] != nil {
                if window[d] == need[d] { valid -= 1 }
                window[d]! -= 1
            }
        }
    }
    return minLen == Int.max ? "" : String(sArr[start..<(start + minLen)])
}

定长滑动窗口

// 模板：固定大小为 k 的窗口
func fixedWindow(_ nums: [Int], _ k: Int) {
    var windowSum = 0
    for i in 0..<nums.count {
        windowSum += nums[i]
        if i >= k {
            windowSum -= nums[i - k]
        }
        if i >= k - 1 {
            // 窗口 [i-k+1, i] 处理
            print("窗口和: \(windowSum)")
        }
    }
}

复杂度

• 时间：O(n)，left 和 right 各最多遍历一次
• 空间：O(k)，k 为字符集大小

3. 经典题目精讲

LeetCode 3 · 无重复字符的最长子串

题意：给定字符串，找不含重复字符的最长子串长度。

思路：扩张右边界，遇到重复字符时收缩左边界直到无重复。

func lengthOfLongestSubstring(_ s: String) -> Int {
    let sArr = Array(s)
    var charIndex: [Character: Int] = [:]
    var left = 0, maxLen = 0
    for right in 0..<sArr.count {
        let ch = sArr[right]
        if let prevIndex = charIndex[ch], prevIndex >= left {
            left = prevIndex + 1
        }
        charIndex[ch] = right
        maxLen = max(maxLen, right - left + 1)
    }
    return maxLen
}

LeetCode 438 · 找到字符串中所有字母异位词

题意：找 s 中所有 p 的异位词子串起始索引。

思路：定长窗口（大小 = p 的长度），比较窗口内字符频率。

func findAnagrams(_ s: String, _ p: String) -> [Int] {
    let sArr = Array(s), pArr = Array(p)
    guard sArr.count >= pArr.count else { return [] }
    var pCount: [Character: Int] = [:]
    var wCount: [Character: Int] = [:]
    for ch in pArr { pCount[ch, default: 0] += 1 }
    for i in 0..<pArr.count {
        wCount[sArr[i], default: 0] += 1
    }
    var result: [Int] = []
    if wCount == pCount { result.append(0) }
    for i in pArr.count..<sArr.count {
        wCount[sArr[i], default: 0] += 1
        let oldChar = sArr[i - pArr.count]
        wCount[oldChar]! -= 1
        if wCount[oldChar] == 0 { wCount.removeValue(forKey: oldChar) }
        if wCount == pCount { result.append(i - pArr.count + 1) }
    }
    return result
}

4. 易错点

• ⚠️ 收缩窗口的循环条件容易写反——求最小窗口在满足条件时收缩，求最大窗口在不满足时收缩
• ⚠️ valid 计数器的增减时机：先判断再加减
• ⚠️ 字符频率比较时注意值为 0 的 key 要删除，否则字典不相等

5. 推荐刷题清单

题号	题名	难度	关键
3	无重复字符最长子串	Medium	不定长窗口
76	最小覆盖子串	Hard	窗口+计数
239	滑动窗口最大值	Hard	单调队列
438	找到所有异位词	Medium	定长窗口
567	字符串排列	Medium	定长窗口

延伸阅读

• LeetCode 官方
• 代码随想录
• 《算法导论》(CLRS)