技术笔记

滑动窗口

Properties2
tags算法, 算法/字符串
aliasesSliding Window

8分钟阅读

滑动窗口（Sliding Window）

📌 定义

滑动窗口是一种用于处理连续子数组/子串问题的算法技巧。通过维护一个窗口（区间），在数组/字符串上滑动，高效地求解满足特定条件的子数组/子串。

核心思路

使用两个指针（left和right）维护一个窗口：

  • right指针：扩大窗口，将元素加入窗口
  • left指针：缩小窗口，将元素移出窗口

通过移动这两个指针，遍历所有可能的窗口，时间复杂度从O(n²)优化到O(n)。

数组: [1, 3, -1, -3, 5, 3, 6, 7]
窗口大小: 3

窗口1: [1, 3, -1]       max=3
窗口2:    [3, -1, -3]    max=3
窗口3:       [-1, -3, 5] max=5
窗口4:          [-3, 5, 3] max=5
...

Go 模板

1. 固定窗口大小

func fixedWindow(arr []int, k int) []int {
    if len(arr) == 0 || k <= 0 {
        return nil
    }
 
    result := make([]int, 0, len(arr)-k+1)
 
    // 1. 初始化窗口状态
    for i := 0; i < k; i++ {
        // add(arr[i])
    }
    // result = append(result, currentAnswer)
 
    // 2. 滑动窗口
    for i := k; i < len(arr); i++ {
        // remove(arr[i-k])
        // add(arr[i])
        // result = append(result, currentAnswer)
    }
 
    return result
}

2. 可变窗口大小（求最大）

func maxVariableWindow(s string) int {
    chars := []rune(s)
    left, best := 0, 0
    window := make(map[rune]int)
 
    for right, ch := range chars {
        window[ch]++
 
        for windowInvalid(window) {
            leftChar := chars[left]
            window[leftChar]--
            if window[leftChar] == 0 {
                delete(window, leftChar)
            }
            left++
        }
 
        if width := right - left + 1; width > best {
            best = width
        }
    }
 
    return best
}

3. 可变窗口大小（求最小）

func minVariableWindow(s string, target string) int {
    chars := []rune(s)
    left := 0
    best := len(chars) + 1
    window := make(map[rune]int)
 
    for right, ch := range chars {
        window[ch]++
 
        for windowValid(window, target) {
            if width := right - left + 1; width < best {
                best = width
            }
 
            leftChar := chars[left]
            window[leftChar]--
            if window[leftChar] == 0 {
                delete(window, leftChar)
            }
            left++
        }
    }
 
    if best == len(chars)+1 {
        return 0
    }
    return best
}

💻 经典问题实现

1. 无重复字符的最长子串

func lengthOfLongestSubstring(s string) int {
    chars := []rune(s)
    left, best := 0, 0
    window := make(map[rune]int)
 
    for right, ch := range chars {
        window[ch]++
        for window[ch] > 1 {
            window[chars[left]]--
            left++
        }
        if width := right - left + 1; width > best {
            best = width
        }
    }
 
    return best
}

2. 最小覆盖子串

func minWindow(s, 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
    start, minLen := 0, len(s)+1
 
    for right := 0; right < len(s); right++ {
        ch := s[right]
        if _, ok := need[ch]; ok {
            window[ch]++
            if window[ch] == need[ch] {
                valid++
            }
        }
 
        for valid == len(need) {
            if width := right - left + 1; width < minLen {
                start = left
                minLen = width
            }
 
            leftChar := s[left]
            if _, ok := need[leftChar]; ok {
                if window[leftChar] == need[leftChar] {
                    valid--
                }
                window[leftChar]--
            }
            left++
        }
    }
 
    if minLen == len(s)+1 {
        return ""
    }
    return s[start : start+minLen]
}

3. 字符串的排列

func checkInclusion(s1, s2 string) bool {
    if len(s1) > len(s2) {
        return false
    }
 
    need := make(map[byte]int)
    for i := 0; i < len(s1); i++ {
        need[s1[i]]++
    }
    window := make(map[byte]int)
    left, valid := 0, 0
 
    for right := 0; right < len(s2); right++ {
        ch := s2[right]
        if _, ok := need[ch]; ok {
            window[ch]++
            if window[ch] == need[ch] {
                valid++
            }
        }
 
        if right-left+1 == len(s1) {
            if valid == len(need) {
                return true
            }
            leftChar := s2[left]
            if _, ok := need[leftChar]; ok {
                if window[leftChar] == need[leftChar] {
                    valid--
                }
                window[leftChar]--
            }
            left++
        }
    }
 
    return false
}

4. 找到字符串中所有字母异位词

func findAnagrams(s, p string) []int {
    if len(p) > len(s) {
        return nil
    }
 
    need := make(map[byte]int)
    for i := 0; i < len(p); i++ {
        need[p[i]]++
    }
    window := make(map[byte]int)
    left, valid := 0, 0
    result := make([]int, 0)
 
    for right := 0; right < len(s); right++ {
        ch := s[right]
        if _, ok := need[ch]; ok {
            window[ch]++
            if window[ch] == need[ch] {
                valid++
            }
        }
 
        if right-left+1 == len(p) {
            if valid == len(need) {
                result = append(result, left)
            }
            leftChar := s[left]
            if _, ok := need[leftChar]; ok {
                if window[leftChar] == need[leftChar] {
                    valid--
                }
                window[leftChar]--
            }
            left++
        }
    }
 
    return result
}

5. 滑动窗口最大值

func maxSlidingWindow(nums []int, k int) []int {
    if len(nums) == 0 || k == 0 {
        return nil
    }
 
    queue := make([]int, 0, len(nums))
    result := make([]int, 0, len(nums)-k+1)
 
    for i := 0; i < len(nums); i++ {
        for len(queue) > 0 && queue[0] < i-k+1 {
            queue = queue[1:]
        }
        for len(queue) > 0 && nums[queue[len(queue)-1]] < nums[i] {
            queue = queue[:len(queue)-1]
        }
        queue = append(queue, i)
 
        if i >= k-1 {
            result = append(result, nums[queue[0]])
        }
    }
 
    return result
}

复杂度分析

操作朴素方法滑动窗口
时间复杂度O(n²) 或 O(n³)O(n)
空间复杂度O(1)O(k)

注：k是窗口大小或字符集大小

经典题目

子串问题

数组问题

固定窗口

⚖️ 优缺点

优点

  • ✅ 高效：将O(n²)优化到O(n)
  • ✅ 简洁：代码模板清晰
  • ✅ 通用：适用于多种子串/子数组问题

缺点

  • ❌ 理解门槛：双指针移动的时机需要理解
  • ❌ 细节多：边界条件容易出错

🎨 应用场景

  1. 子串/子数组问题：求满足条件的连续区间
  2. 字符串匹配：模式匹配
  3. 数据流处理：固定窗口的统计
  4. 网络流量控制：滑动窗口协议

💡 滑动窗口的关键点

1. 什么时候用滑动窗口？

  • ✅ 问题涉及连续的子数组/子串
  • ✅ 需要优化暴力O(n²)的解法
  • ✅ 窗口的移动是单调的

2. 如何移动窗口？

for right := 0; right < len(arr); right++ {
    add(arr[right])
 
    for needShrink() {
        remove(arr[left])
        left++
    }
}

3. 何时更新答案？

  • 求最大：收缩窗口之前更新
  • 求最小：窗口满足条件时更新
  • 固定窗口：窗口形成时更新

💡 滑动窗口 vs 双指针

特性滑动窗口双指针
应用连续子数组/子串数组/链表问题
窗口动态或固定窗口不一定是窗口
方向单向滑动可以对撞或同向
例子最长无重复子串两数之和、回文判断

相关主题

返回：字符串算法 | 算法学习导航

关系图谱

反向链接