1. 基础
1.1. 定义
数组（Array）是一种线性表数据结构，它用一组连续的内存空间，来存储相同类型的数据。
1.2. 时间复杂度
1.2.1. 查询
当计算给每个内存单元分配一个地址，计算机通过地址来访问数据。
寻址公式如下：
a[i]_address = base_address + i * data_type_size
arr[i] 首地址 = 数组内存块首地址 + 数据类型大小 * i ，其中i为偏移量
base_address：内存块的首地址
data_type_size：数组中每个元素的大小，比如每个元素大小是4个字节
1.2.2. 插入
最好
数组若无序，插入新的元素时，可以将第 k 个位置元素移动到数组末尾，把新的元素，插入到第 k 个位置，此处复杂度为 O(1)。
最坏
从数组开头插入数据，所有的数据往后移一位，情况最差，时间复杂度为 O(n)。
1.2.3. 删除
最好
数组若无序，删除第 k 个位置元素，第 k 个元素先与最后的元素交换， 然后删除最后一个元素。
最坏
从数组开头删除数据，所有的数据往前移一位，情况最差，时间复杂度为 O(n)。
1.2. 注意事项
- 警惕数组的访问越界问题
2.进阶
2.1. 标记清除思想
将多次删除操作中集中在一起执行，可以先记录已经删除的数据，但是不进行数据迁移，而仅仅是记录，当发现没有更多空间存储时，再执行真正的删除操作，这样减少数据搬移次数节省耗时。
2.2. 数组&容器
使用数组
- 如果已知数据大小，且涉及的数据操作比较简单。
- 存储基本类型
- 追求性能
使用容器
- 业务开发
2.3. 【思考】为什么数组要从 0 开始编号，而不是1？
- 历史原因
- 对于
CPU从 1 开始的寻址公式a[i]_address = base_address + (i - 1) * data_type_size，比从 0 开始的寻址公式多了一次减法指令。
3. 练习题
双指针：使用两个相反方向或相同方向的指针扫描数组
- 【相反方向】求排序数组中的两个数字之和
- 【相同方向】正数数组中子数组的和或乘积
3.1. 相反方向
6.排序数组中的两个数字之和
- 解法一：暴力。固定一个数字，再依次判断数组中其余数字与它的和是不是等于
k - 解法二：二分查找。固定一个数字 ，另外一个数字用二分法查找
k-i - 解法三：空间换时间。所有数字都放入哈希表中 ，扫描到
i，判断哈希中是否存在k-i -
【最优】解决四：双指针-相反方向。左
i，右j，大于目标数向左移动j，小于目标数向右移动i
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
int i = 0;
int j = numbers.size() - 1;
vector<int> ret;
while (i < j && numbers[i] + numbers[j] != target) {
if (numbers[i] + numbers[j] > target) {
j--;
} else {
i++;
}
}
ret.push_back(i);
ret.push_back(j);
return ret;
}
};
