数组是什么：连续内存 + 下标
数组就像一排编号的储物柜，每个柜子只能放一件物品。所有柜子紧挨着，在内存中占据一块连续的空间。每个柜子有一个固定的下标（从0开始），通过下标就能直接找到对应的柜子。
随机访问为什么是 O(1)
因为数组元素在内存中连续存放，计算机知道数组的起始地址和每个元素的大小。要访问下标为 i 的元素，只需计算 起始地址 + i × 元素大小，一步就能定位。无论数组多大，计算时间都一样，所以时间复杂度是 O(1)。
增：末尾追加 vs 中间插入 vs 扩容
- 末尾追加：如果数组还有空位，直接放在最后，O(1)。
- 中间插入：需要把插入位置后面的所有元素依次向后移动一位，腾出空位，平均需要移动一半元素，O(n)。
- 扩容：当数组满了，需要申请一块更大的连续内存（通常是原大小的两倍），把原数组所有元素复制过去，再释放旧空间，O(n)。
删：末尾 vs 中间
- 删除末尾：直接移除最后一个元素，不需要移动其他元素，O(1)。
- 删除中间：删除后，后面的所有元素需要向前移动一位填补空缺，平均移动一半元素，O(n)。
增删查改复杂度小结表
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 随机访问（查/改） | O(1) | 通过下标直接计算地址 |
| 末尾追加 | O(1) | 有空间时 |
| 末尾删除 | O(1) | 直接移除 |
| 中间插入 | O(n) | 需要移动元素 |
| 中间删除 | O(n) | 需要移动元素 |
| 扩容 | O(n) | 复制全部元素 |
静态数组 vs 动态数组（各语言）
静态数组：创建时大小固定，不能改变。例如 C 的 int arr[10]、Java 的 int[] arr = new int[10]。
动态数组：大小可以自动增长，内部自动管理扩容。例如 C++ 的 std::vector、Java 的 ArrayList、Python 的 list、JavaScript 的 Array。它们底层仍然是连续内存的数组，但封装了扩容逻辑，让开发者用起来更方便。