一、数组是什么
数组（Array）是一种把相同类型的数据按顺序存放在连续内存空间中的数据结构。
核心特点
- 元素类型通常一致
- 内存空间连续
- 可以通过下标直接访问元素
- 适合顺序存储和按位置访问
生活类比
数组就像一排连续编号的储物柜：
- 柜子编号 = 下标
- 柜子里的东西 = 数组元素
- 想找某个元素时，只要知道编号，就能快速找到
二、数组为什么重要
数组是最基础、最常见的数据结构之一。 很多算法问题、很多复杂数据结构，底层都和数组有关。
常见用途
- 存成绩、温度、价格等一组同类数据
- 作为排序、查找等算法的基础载体
- 表示连续时间序列数据
- 表示二维结构，如表格、矩阵、地图、棋盘
- 作为其他数据结构实现的基础
三、数组的常见操作
1. 访问
通过下标直接取值。
例如：
arr[0]arr[3]
特点：非常快。
2. 遍历
把数组从头到尾看一遍。
常见用途：
- 求和
- 找最大值
- 统计次数
- 打印全部元素
3. 查找
判断某个元素是否存在，或者找它的位置。
分两种情况：
- 无序数组：通常只能一个个找
- 有序数组：可以考虑二分查找
4. 修改
直接替换某个位置上的值。
例如：
arr[2] = 10
5. 插入
在某个位置加入一个新元素。
特点：
- 末尾插入相对简单
- 中间插入通常需要移动后面的元素
6. 删除
移除某个位置上的元素。
特点：
- 删除末尾元素相对容易
- 删除中间元素通常需要让后面的元素前移
7. 排序
把数组按某种规则排列，比如从小到大。
8. 合并
把两个数组拼接或按规则合并成一个新数组。
四、数组的性能与时间复杂度
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 按下标访问 | O(1) | 直接定位 |
| 按下标修改 | O(1) | 已知位置直接替换 |
| 遍历 | O(n) | 逐个查看元素 |
| 无序查找 | O(n) | 可能扫描全部 |
| 有序数组二分查找 | O(log n) | 每次缩小一半范围 |
| 中间插入 | O(n) | 后续元素后移 |
| 中间删除 | O(n) | 后续元素前移 |
重点理解
数组的优点和缺点都来自“连续存储”。
- 优点：访问快
- 缺点：中间插入和删除慢
类比
像一排摆整齐的书：
- 找第 20 本很快
- 但往第 3 本前塞一本书，要把后面的书整体挪开
五、数组常见题型
1. 遍历统计类
例如：
- 求和
- 最大值 / 最小值
- 统计出现次数
- 判断是否满足条件
2. 查找定位类
例如：
- 找目标值
- 找重复元素
- 找缺失元素
- 找第一个/最后一个出现的位置
3. 双指针类
例如：
- 两数之和（有序数组）
- 删除重复元素
- 移动零
- 反转数组
4. 滑动窗口类
例如：
- 最长满足条件的连续子数组
- 最短满足条件的连续子数组
5. 前缀和类
例如：
- 快速求某段区间的和
- 子数组和相关问题
6. 子数组 / 区间类
例如：
- 最大子数组和
- 连续递增子数组
- 区间统计
7. 排序与合并类
例如：
- 合并有序数组
- 区间合并
- 第 k 大元素
8. 原地操作类
例如：
- 原地删除元素
- 原地去重
- 原地交换
9. 矩阵类问题
数组扩展到二维后会出现：
- 矩阵遍历
- 矩阵旋转
- 搜索二维数组
六、数组解题技巧
1. 暴力遍历
最直接的方法，适合先把题做对。
2. 双指针
两个指针一起工作。
常见形式：
- 左右指针
- 快慢指针
适合：
- 有序数组
- 原地修改
- 压缩、去重、移动元素
3. 滑动窗口
适合处理“连续区间”问题。
识别信号：
- 最长连续……
- 最短连续……
- 满足条件的子数组……
4. 前缀和
适合频繁求区间和。
核心思想：
- 提前保存从开头到当前位置的累计和
- 之后用减法快速得到区间和
5. 排序
先排序，再处理。
好处：
- 更容易找规律
- 更容易去重
- 更容易使用双指针
6. 二分查找
适用于有序数组。
特点：
- 每次排除一半
- 常用于找值、找边界
7. 原地修改
不额外开大空间，直接在原数组操作。
注意点：
- 覆盖问题
- 下标顺序
- 是否会丢失未处理数据
8. 哈希辅助
用空间换时间。
适合：
- 判断是否存在
- 统计频率
- 找配对关系
9. 状态维护
边遍历边记录关键信息。
例如：
- 当前最大值
- 当前最优解
- 当前区间状态
七、做数组题的判断思路
拿到一道数组题时，可以按以下顺序思考：
- 是否只需要遍历？
- 数组是否有序？
- 是否是连续区间问题？
- 是否适合双指针？
- 是否需要频繁求区间和？
- 是否可以先排序？
- 是否能用哈希优化？
- 是否要求原地修改？
这是一套很实用的“题目识别框架”。
八、学习数组时的常见易错点
1. 下标越界
数组通常从 0 开始计数，要特别注意边界。
2. 空数组
有些题如果数组为空，会直接报错。
3. 只有一个元素
单元素情况常常是特殊边界。
4. 左右指针是否相遇
双指针题里容易写错停止条件。
5. 删除/插入后的长度变化
操作后要注意新的有效区间。
6. 重复元素处理
尤其在去重、查找边界时要格外小心。
九、学习建议
1. 先理解本质，再记方法
不要只背定义，要理解：
- 为什么访问快
- 为什么插删慢
- 为什么有序适合二分
- 为什么连续区间常用滑动窗口
2. 先学操作和复杂度，再刷题
推荐顺序：
- 定义
- 常见操作
- 时间复杂度
- 题型
- 技巧
- 刷题总结
3. 做题要分类
不要把每道题当成全新的题。 要学会识别它属于哪一类。
4. 多画图
数组题非常适合画图。 特别是：
- 双指针
- 滑动窗口
- 插入删除
- 前缀和
5. 建立“题型—方法”映射
例如：
- 有序数组 → 二分 / 双指针
- 连续区间 → 滑动窗口 / 前缀和
- 是否存在 / 频率统计 → 哈希
- 原地操作 → 双指针 / 交换 / 覆盖
十、最终总结
数组是算法学习中最基础的数据结构之一。 它的核心优势是：
- 访问快
- 结构简单
- 适合顺序处理
- 很多算法技巧都建立在数组之上
但它也有明显限制：
- 中间插入和删除效率较低
所以，学习数组最关键的不是只记住定义， 而是建立这样一个完整认知：
数组是什么 → 能做什么 → 快在哪里 → 慢在哪里 → 常怎么考 → 遇题怎么解
十一、数组速记版
定义
数组：连续存储、同类型、可按下标访问的数据结构。
优点
- 访问快 O(1)
- 结构简单
- 易于遍历
缺点
- 中间插入删除慢 O(n)
- 长度通常不够灵活
高频题型
- 遍历统计
- 查找定位
- 双指针
- 滑动窗口
- 前缀和
- 排序合并
- 原地操作
- 矩阵问题
高频方法
- 遍历
- 双指针
- 滑动窗口
- 前缀和
- 排序
- 二分
- 哈希
- 状态维护