数组专题导读
从这篇开始进入第一个正式的数据结构专题：数组。它是最基础的结构，但别因此小看它——二分、双指针、滑动窗口、前缀和这些贯穿整个算法学习的核心套路，全都是在数组上练出来的。
数组是是什么：内存连续的代价与红利
数组在内存中占据一块连续空间，这个底层特性决定了它的一切行为：
下标: 0 1 2 3 4
地址: 1000 1004 1008 1012 1016 （int 每个 4 字节）
值 : [ 7 ] [ 3 ] [ 9 ] [ 5 ] [ 1 ]因为连续，知道首地址和下标就能直接算出元素地址：地址 = 首地址 + 下标 × 元素大小。于是得到数组的一体两面：
| 操作 | 复杂度 | 原因 |
|---|---|---|
| 按下标访问 | O(1) | 地址直接算出来，不用遍历 |
| 按值查找（无序） | O(n) | 只能逐个比对 |
| 尾部插入/删除 | O(1)（不考虑扩容） | 不挪动其他元素 |
| 中间插入/删除 | O(n) | 后续元素整体搬运 |
在 Java 里，int[] 是真数组，ArrayList 是"数组 + 自动扩容"的封装，二者增删改查的复杂度模型一致。为什么增删要整体搬运？因为内存必须连续，删掉中间一个元素，后面的元素就要挨个往前补——这也是后面"移除元素"题目的物理背景。
一句话记住：数组用"内存连续"换来 O(1) 随机访问，代价是增删要 O(n)。
Java 选手还要分清 int[] 与 ArrayList<Integer> 的取舍：
| 维度 | int[] | ArrayList<Integer> |
|---|---|---|
| 存储内容 | 原始 int，无装箱 | Integer 对象引用，有装箱开销 |
| 容量 | 固定，创建时定死 | 动态扩容（约 1.5 倍增长） |
| 随机访问 | O(1)，无间接层 | O(1)，但多一层对象寻址 |
| 常用工具 | Arrays.sort / copyOf 等 | add / get / contains 等方法 |
刷题的实用建议：长度确定或需要极致性能时用原生数组（尤其 LeetCode 的入参多为数组），长度未知、频繁增删时用 ArrayList。另外注意 Arrays.asList() 返回的是固定长度视图，不能 add/remove——这是 Java 刷题的高频坑。
专题知识地图
数组专题按下面的顺序学习，每一类题都对应一个可复用的解题框架：
1. 二分查找
前提：数组有序 + 可随机访问。核心是每轮用中间元素把搜索范围砍半，从 O(n) 降到 O(logn)。
看着简单，坑全在边界上：while 里写 < 还是 <=、右边界更新成 mid 还是 mid - 1。解法是建立循环不变量——明确"待查区间"的定义，让所有代码与定义自洽。
代表题：704 二分查找。
2. 移除元素（快慢指针）
题目要求原地删除数组中所有等于某值的元素，返回新长度。由于数组不能真正"删"，只能用快慢双指针：快指针探路，慢指针守着"已保留区"的边界，把不删的元素搬到前面。
这是双指针思想的第一次落地，后面链表、字符串专题会反复用到同款套路。
代表题：27 移除元素、283 移动零。
3. 有序数组平方
非递减数组的元素有负数，平方后最大值只可能出现在两端。解法是两端向中间的双指针：每次挑两端平方值中更大的放进结果数组的尾部，一趟 O(n) 完成。
考点：不能死板地对负数排序，要利用"原数组有序"这个信息。
代表题：977 有序数组的平方。
4. 长度最小子数组（滑动窗口）
找"和 ≥ target 的最短连续子数组"。暴力枚举所有子数组是 O(n²)，滑动窗口用一右一左两个指针把整体压到 O(n)：右指针扩张累加，满足条件后左指针收缩求最短。
适用条件很明确：连续子数组 + 窗口内指标随扩缩单调变化。这个模型后面在字符串题（76 最小覆盖子串）还会升级。
代表题：209 长度最小的子数组、76 最小覆盖子串。
5. 螺旋矩阵（模拟）
按顺时针螺旋顺序填充/读取 n×n 矩阵。没有巧妙算法，纯考模拟的边界控制：坚持"左闭右开"的区间规则，一圈拆成上、右、下、左四条边分别处理，每条边"留头去尾"，防止重复填充。
考点：循环不变量（填充区间的自洽定义）+ 耐心。
代表题：59 螺旋矩阵 II。
6. 前缀和
预处理出一个前缀和数组 pre[i] = nums[0] + ... + nums[i-1]，之后任意区间和 sum[i..j] = pre[j+1] - pre[i] 用 O(1) 拿到。适合"多次区间查询"的场景，也常和哈希表配合解决"和为 K 的子数组"。
代表题：303 区域和检索、560 和为 K 的子数组。
知识地图一图流
数组特性（连续内存：访问 O(1)，增删 O(n)）
│
├── 有序数组 ──→ 二分查找（704/35/34/69）
├── 原地修改 ──→ 快慢指针（27/283）
├── 两端有序 ──→ 相向双指针（977）
├── 连续子数组 ─→ 滑动窗口（209/76）
├── 区间求和 ──→ 前缀和（303/560）
└── 矩阵遍历 ──→ 边界模拟（59）六类框架的复杂度与适用信号汇总成一张表，做题时对照着用：
| 框架 | 时间 | 额外空间 | 前提信号 |
|---|---|---|---|
| 二分查找 | O(logn) | O(1) | 数组有序 + 可随机访问 |
| 快慢指针 | O(n) | O(1) | 原地增删、分区覆盖 |
| 相向双指针 | O(n) | O(1)（977 需结果数组 O(n)） | 从两端看单调择优 |
| 滑动窗口 | O(n) | O(k)，k 为窗口状态量 | 连续子数组 + 指标单调 |
| 前缀和 | 预处理 O(n)，查询 O(1) | O(n) | 多次区间和查询 |
| 螺旋模拟 | O(n²) | O(1)（不含结果矩阵） | 矩阵按规则填充 |
LeetCode 题单清单
建议按表格顺序刷，前面的题是后面题的铺垫：
| 题号 | 题名 | 一句话考点 |
|---|---|---|
| 704 | 二分查找 | 闭区间/半开区间两种写法与循环不变量 |
| 35 | 搜索插入位置 | 二分找到"第一个 ≥ target 的位置" |
| 34 | 在排序数组中查找元素的第一个和最后一个位置 | 左右边界二分，最容易写崩的模板题 |
| 69 | x 的平方根 | 二分答案思想，注意 mid 防溢出 |
| 27 | 移除元素 | 快慢指针原地覆盖 |
| 283 | 移动零 | 快慢指针变形，保留的元素换成非零 |
| 977 | 有序数组的平方 | 两端向中间比较，结果从尾部填 |
| 209 | 长度最小的子数组 | 滑动窗口模板题 |
| 59 | 螺旋矩阵 II | 四条边循环 + 左闭右开区间模拟 |
| 303 | 区域和检索 - 数组不可变 | 前缀和预处理 + O(1) 查询 |
| 560 | 和为 K 的子数组 | 前缀和 + 哈希表统计 |
学习建议
- 每类框架先写最裸的模板，不看题解独立敲一遍，再去套具体题目。
- 动手模拟边界：用长度为 1 的数组、目标在首/尾、目标不存在这些极端用例手推一遍代码，比看十遍文字都管用。
- 一题多解对比复杂度：比如 209 先写暴力 O(n²) 再改滑窗 O(n)，感受框架带来的提升，比直接背模板理解深得多。
易错点清单
- 混淆"下标"和"位置"：二分、滑窗里下标是 0-based，窗口长度是
right - left + 1而不是right - left。 - 前缀和数组忘记多留一位哨兵，导致
left = 0的区间查询越界。 - 原地操作时先用新数组"偷懒"，忽略了题目 O(1) 空间的要求。
- 螺旋矩阵不定义区间规则就开写，角格重复填充。
- 只顾刷题不复盘：AC 之后说不出复杂度，等于没有收获。
下一篇正式展开二分查找，把"循环不变量"这个控制边界的思想讲透。