知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 01 - 滑动窗口模板 ## 什么是滑动窗口 用两个指针 left 和 right 维护一个窗口,right 不断右移扩大窗口,当窗口满足/不满足某个条件时,left 右移缩小窗口。 ``` 数组:[a, b, c, d, e, f, g] ↑ ↑ left right └── 窗口 ──┘ ``` 本质是把暴力的 O(n²) 优化到 O(n):right 和 left 各最多走 n 步。 ## 万能模板 ```java int left = 0; for (int right = 0; right < n; right++) { // 1. 右指针元素进入窗口,更新窗口状态 window.add(arr[right]); // 2. 判断是否需要收缩窗口 while (窗口需要收缩) { // 3. 左指针元素离开窗口,更新窗口状态 window.remove(arr[left]); left++; } // 4. 在这里更新答案(根据题意,可能在 while 里面更新) ans = Math.max(ans, right - left + 1); } ``` ## 两种类型 ``` 类型 1:求最长(最大窗口) 窗口不满足条件时收缩 在收缩后更新答案 例:无重复字符的最长子串 类型 2:求最短(最小窗口) 窗口满足条件时收缩 在收缩过程中更新答案 例:最小覆盖子串、长度最小的子数组 ``` ## 一句话总结 右指针扩张探索,左指针收缩优化。两个指针各走一遍,O(n) 搞定。 --- 下一篇:[02 - 无重复字符的最长子串](./02-longest-substring.md)
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入