跳转至

滑动窗口

滑动窗口(Sliding Window)是一种高效处理区间类问题的算法技巧,常用于字符串、数组等线性结构,适合查找满足条件的最长/最短子区间、子串等。


典型应用场景

  • 最长/最短无重复子串(LeetCode 3)
  • 固定/变长区间的和、乘积、计数(LeetCode 209、713)
  • 子数组/子串满足某种条件的统计(LeetCode 76、438)
  • 连续区间的最大/最小值

基本模式

固定窗口长度

适用于窗口长度已知的场景。

1
2
3
4
5
6
7
for right := 0; right < len(nums); right++ {
    // 扩展窗口
    if right - left + 1 > k {
        left++ // 收缩窗口
    }
    // 统计/处理窗口
}

可变窗口长度

适用于窗口长度不固定,需要根据条件动态收缩。

优势

  • 时间复杂度低,通常 \(O(n)\)
  • 空间复杂度低,常用哈希表/计数器辅助
  • 代码简洁,易于维护

注意事项

  • 正确维护窗口边界(left/right)
  • 动态更新窗口内的状态(如哈希表、计数器)
  • 处理窗口收缩时的边界和条件

经典题目