罗罗编程学习记录
本页内容 展开查看

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 的子数组
  • [ ] 能用差分完成批量区间加减并还原
  • [ ] 能写出二维前缀和四角容斥公式
  • [ ] 能说清三数之和的排序、双指针与去重细节
  • [ ] 每题能报出时间、空间与口径,并列边界用例