数组
数组（Array）是最基础、最重要的线性数据结构——一段连续内存里顺序存放一组同类型元素，靠**下标（index）**在 O(1) 时间内随机访问任一元素。几乎所有高级语言都把它作为一等内建类型（C 的 int[]、Java 的 int[]、Python 的 list、JavaScript 的 Array、Go 的 slice 底层数组），动态数组（C++ vector、Java ArrayList、JS Array）进一步在「满则扩容」策略下兼具了可变长度与摊还 O(1) 尾插。它既是链表、栈、队列、堆、哈希表（开放寻址法）的底层载体，也是顺序表、矩阵、字符串的物理实现，地位相当于数据结构里的「地基」。
数组的全部考点都源于一个物理事实：内存连续 ⇒ O(1) 随机访问 + O(n) 插入删除。由此衍生出三大主题：①动态数组与扩容策略（几何扩容 / 摊还分析 / 容量与长度的区别）；②数组上的经典算法（双指针、滑动窗口、前缀和、差分数组）；③多维数组（矩阵）的存储与遍历（行主序 / 螺旋矩阵 / 矩阵转置）。其中双指针（对撞、快慢、分离）与滑动窗口是面试高频套路，前缀和把区间求和从 O(n) 降到 O(1)，差分数组把区间修改从 O(n) 降到 O(1)——它们本质都是利用「连续可随机访问」这一性质做时空权衡。
评价
优点
- O(1) 随机访问：连续内存 + 下标直接算地址（
base + index × size），读、按下标改都是常数时间——这是数组区别于链表的核⼼优势 - 缓存友好（cache-friendly）：连续存放命中 CPU 缓存行，顺序遍历比链表快一个数量级（即使两者大 O 相同）
- 实现简单、常数因子小：无需存指针，内存开销仅数据本身；动态数组摊还 O(1) 尾插尾删
- 承载面广：栈/队列（两端操作）、堆（完全二叉树映射）、哈希表（开放寻址）、字符串（字符数组）都以它为底层
缺点
- 插入删除 O(n)：中间插入/删除要搬移后续所有元素（链表只需改指针）——这是数组最大的硬伤
- 静态数组容量固定：超容需扩容（申请新块 + 拷贝），单次扩容 O(n)；动态数组用几何扩容把摊还成本压到 O(1)，但峰值内存是元素数的 ~2 倍
- 内存必须连续：申请大数组可能因碎片化失败；不支持零散存储
本叶地图
- 入门 —— 定位与物理模型、静态 vs 动态数组、动态数组扩容与摊还分析、与链表怎么选、JS/Python 数组是真数组吗
- 双指针与滑动窗口 —— 对撞/快慢/分离三类双指针、滑动窗口框架、无重复最长子串、最小覆盖子串
- 前缀和与差分 —— 一维/二维前缀和、区间求和 O(1)、差分数组区间修改 O(1)
- 矩阵遍历 —— 行主序存储、螺旋矩阵、矩阵旋转、之字形遍历
- 参考 —— 数组 API 速查、复杂度表、双指针套路清单、易错点
交互演示
- 数组可视化演示 —— 数组的连续内存布局与下标访问