02｜数组与查找表
1. 核心概念
数组将相同类型的元素连续存放在内存中，通过下标直接定位元素。
- 连续存储：相邻元素在内存中依次排列，通常有利于顺序遍历和缓存访问。
- 随机访问：已知合法下标时，无需遍历前面的元素，访问时间复杂度为 O(1)。
- 按值查找：在无序数组中查找某个值，通常仍需逐项比较，时间复杂度为 O(n)。
2. 容量与有效长度
- 容量（Capacity）：最多能够存储的元素数量。
- 有效长度（Length）：当前已经使用的元素数量，通常满足
0 ≤ Length ≤ Capacity。 - 有效范围：下标从
0到Length - 1；未使用的空间不应被当作有效数据。
固定容量数组不能超出预设空间；可扩容数组则可能在空间不足时重新分配并复制数据。
3. 常见操作与成本
| 操作 | 典型时间复杂度 | 原因 |
|---|---|---|
| 按下标访问 | O(1) | 直接计算目标位置 |
| 遍历 / 无序按值查找 | O(n) | 最坏需检查全部有效元素 |
| 尾部追加（容量足够） | O(1) | 直接写入下一个位置 |
| 中间插入或删除 | O(n) | 通常需要移动后续元素 |
数组中间插入示意：
flowchart TD
A["原数组：10｜20｜30｜40｜空"]
B["将 30、40 向右移动"]
C["插入后：10｜20｜99｜30｜40"]
A --> B --> C4. 查找表（Lookup Table）
查找表通过键或编号定位对应的数据。
- 直接索引：编号可映射为合法数组下标时，可以 O(1) 查找。
- 边界检查：必须确认编号在有效范围内，并处理空槽位或不存在的编号。
- 空间权衡：编号非常稀疏时，直接建立大数组可能浪费内存。
查找表是一种查找组织方式，不局限于数组实现。
5. 适用场景与限制
适合：数量可控、频繁按位置访问或遍历、很少中间插删的数据，例如固定配置表和连续数据样本。
限制：中间插删通常需要移动元素；固定容量存在上限；动态扩容可能带来重新分配和复制成本。
6. 总结
数组的主要优势是连续存储与 O(1) 下标访问；选择数组时，要同时考虑有效长度、容量限制和元素移动成本。