02.2.1 数组与双指针滑窗
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.2 数组、字符串与哈希
这个知识域解决什么问题
数组是面试最高频的载体。本知识域围绕一条主线展开:原地划分与双指针 → 连续区间的滑动窗口 → 区间统计的前缀和与差分 → 二维矩阵与排序配合双指针。所有框架都要求先讲清指针/状态为什么这样移动,再给可运行代码与边界用例。
知识地图
数组原地操作与快慢双指针(1)
→ 滑动窗口模板与边界(2)
→ 前缀和与差分(3)
→ 二维矩阵与排序配合双指针(4)
子主题
| 编号 | 子主题 | 核心内容 | 题数 |
|---|---|---|---|
| 02.2.1.1 | 数组原地操作与快慢双指针 | 随机访问、移除元素、移动零、去重、合并有序数组、颜色分类、轮转、相向/快慢指针、越界与稳定性 | 20 |
| 02.2.1.2 | 滑动窗口模板与边界 | 可变/定长窗口、无重复子串、最小覆盖子串、窗口状态维护、收缩条件、负数影响、窗口最值、复杂度推导 | 20 |
| 02.2.1.3 | 前缀和与差分 | 一维前缀和、和为 K 子数组、前后缀积、差分区间加减、二维前缀和与差分、选型与溢出 | 20 |
| 02.2.1.4 | 二维矩阵与排序配合双指针 | 旋转/螺旋/置零/对角线、矩阵二分与右上角查找、三/四数之和、区间合并、排序前提与复杂度 | 20 |
合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,标注复杂度口径与边界条件。
学习路径
先 1 掌握原地划分与两类双指针,再 2 练熟滑动窗口的扩张-收缩模板与边界,3 学会前缀和/差分把区间操作降到 O(1),最后 4 处理二维矩阵与排序后双指针的组合题。
自检
- [ ] 能写快慢指针原地保留与相向双指针夹逼模板
- [ ] 能区分可变窗口与定长窗口的更新时机
- [ ] 能用前缀和 + 哈希统计和为 K 的子数组
- [ ] 能用差分完成批量区间加减并还原
- [ ] 能写出二维前缀和四角容斥公式
- [ ] 能说清三数之和的排序、双指针与去重细节
- [ ] 每题能报出时间、空间与口径,并列边界用例