数组分为两大类，一类是静态数组，一类是动态数组。
静态数组就是一块连续的内存空间，我们可以通过索引来访问这块内存空间中的元素，这才是数组的原始形态。
而动态数组是编程语言为了方便我们使用，在静态数组的基础上帮我们添加了一些常用的 API，比如 push, insert, remove 等等方法，这些 API 可以让我们更方便地操作数组元素，不用自己去写代码实现这些操作。
有了动态数组，后面讲到的队列、栈、哈希表等复杂数据结构都会依赖它进行实现。
静态数组
静态数组在创建的时候就要确定数组的元素类型和元素数量。
静态数组的用法比较原始，写算法题也没必要用，我们一般直接用动态数组。但为了理解原理，在这里还是要讲解一下。
定义一个静态数组的方法如下：
// 定义一个大小为 10 的静态数组
int arr[10];
// 用 memset 函数把数组的值初始化为 0
memset(arr, 0, sizeof(arr));
// 使用索引赋值
arr[0] = 1;
arr[1] = 2;
// 使用索引取值
int a = arr[0];
1、在内存中开辟了一段连续的内存空间，大小是 10 * sizeof(int) 字节。一个 int 在计算机内存中占 4 字节，也就是总共 40 字节。
2、定义了一个名为 arr 的数组指针，指向这段内存空间的首地址。
那么 arr[1] = 2 这段代码又做了什么事情呢？主要有这么几件事：
A、计算 arr 的首地址加上 1 * sizeof(int) 字节（4 字节）的偏移量，找到了内存空间中的第二个元素的首地址。
B、从这个地址开始的 4 个字节的内存空间中写入了整数 2。
所以，我们获得了数组的超能力 随机访问：只要给定任何一个数组索引，我可以在 O(1) 的时间内直接获取到对应元素的值。
因为我可以通过首地址和索引直接计算出目标元素的内存地址。计算机的内存寻址时间可以认为是 O(1)，所以数组的随机访问时间复杂度是 O(1)。
但是，一个人最大的优势往往也是他的最大劣势。数组连续内存的特性给了他随机访问的超能力，但它也因此吃了不少苦,下面介绍。
增删查改
数据结构的职责就是增删查改，再无其他。
那么刚刚介绍数组这种数据结构的底层原理，我们其实只介绍了 查 和 改 的部分，也就是通过索引修改和访问对应元素的值。那么 增删 这两个操作又是如何实现的呢？
增
情况一，数组末尾追加（append）元素
比方说，我有一个大小为 10 的数组，里面装了 4 个元素，现在想在末尾追加一个元素，怎么办？
比较简单，直接在对应的索引赋值就行了，这是大概的代码逻辑：
// 大小为 10 的数组已经装了 4 个元素
int arr[10];
for (int i = 0; i < 4; i++) {
arr[i] = i;
}
// 现在想在数组末尾追加一个元素 4
arr[4] = 4;
// 再在数组末尾追加一个元素 5
arr[5] = 5;
// 依此类推
// ...
可以看到，由于只是对索引赋值，所以在数组末尾追加元素的时间复杂度是 O(1)。
情况二，数组中间插入（insert）元素
比方说，我有一个大小为 10 的数组 arr，前 4 个索引装了元素，现在想在第 3 个位置（索引 2 arr[2]）插入一个新元素，怎么办？
这就要涉及 数据搬移，给新元素腾出空位，然后再才能插入新元素。大概的代码逻辑是这样的：
// 大小为 10 的数组已经装了 4 个元素
int arr[10];
for (int i = 0; i < 4; i++) {
arr[i] = i;
}
// 在索引 2 置插入元素 666
// 需要把索引 2 以及之后的元素都往后移动一位
// 注意要倒着遍历数组中已有元素避免覆盖
for (int i = 4; i > 2; i--) {
arr[i] = arr[i - 1];
}
// 现在第 3 个位置空出来了，可以插入新元素
arr[2] = 666;
情况三，数组空间已满
静态数组在创建时就要确定大小，比方说现在我创建了一个数组 int arr[10]（一块 40 字节的连续内存空间），然后往里面存了 10 个元素，这时候我想再插入一个元素，怎么办？无论是追加在尾部还是插入到中间，都没有位置留给新元素了。
有的同学可能说，这个简单呀，在这 40 字节后面再加上 4 个字节的连续内存空间，用来存储新的元素，不就行了吗？
不行的，连续内存必须一次性分配，分配完了之后就不能随意增减了。因为你这块连续内存后面的内存空间可能已经被其他程序占用了，不能说你想要就给你。
那怎么办呢？只能重新申请一块更大的内存空间，把原来的数据复制过去，再插入新的元素，这就是数组的「扩容」操作。
比方说，我重新创建一个更大的数组 int arr[20]，然后把原来的 10 个元素复制过去，这样就有空余位置插入新的元素了。
大概的逻辑是这样的：
// 大小为 10 的数组已经装满了
int arr[10];
for (int i = 0; i < 10; i++) {
arr[i] = i;
}
// 现在想在数组末尾追加一个元素 10
// 需要先扩容数组
int newArr[20];
// 把原来的 10 个元素复制过去
for (int i = 0; i < 10; i++) {
newArr[i] = arr[i];
}
// 在新的大数组中追加新元素
newArr[10] = 10;
删
删除元素的操作和增加元素的操作类似，也需要分情况讨论。
情况一，删除末尾元素
比方说，我有一个大小为 10 的数组，里面装了 5 个元素，现在想删除末尾的元素，怎么办？
很简单，直接把末尾元素标记为一个特殊值代表已删除就行了，我们这里简单举例，就用 -1 作为特殊值代表已删除好了。删除数组尾部元素的本质就是进行一次随机访问，时间复杂度是 O(1)。
大概的代码逻辑是这样的：
// 大小为 10 的数组已经装了 5 个元素
int arr[10];
for (int i = 0; i < 5; i++) {
arr[i] = i;
}
// 删除末尾元素，暂时用 -1 代表元素已删除
arr[4] = -1;
情况二，删除中间元素
比方说，我有一个大小为 10 的数组，里面装了 5 个元素，现在想删除第 2 个元素（arr[1]），怎么办？
这也要涉及 数据搬移，把被删元素后面的元素都往前移动一位，保持数组元素的连续性。
大概的代码逻辑是这样的：
// 大小为 10 的数组已经装了 5 个元素
int arr[10];
for (int i = 0; i < 5; i++) {
arr[i] = i;
}
// 删除 arr[1]
// 需要把 arr[1] 之后的元素都往前移动一位
// 注意要正着遍历数组中已有元素避免覆盖，不懂的话请看下方可视化面板
for (int i = 1; i < 4; i++) {
arr[i] = arr[i + 1];
}
// 最后一个元素置为 -1 代表已删除
arr[4] = -1;
在数组中间删除元素的时间复杂度是 O(N)，因为涉及到数据搬移。
总结
综上，静态数组的增删查改操作的时间复杂度是：
- 增：
- 在末尾追加元素：O(1)。
- 在中间（非末尾）插入元素：O(N)。
- 删：
- 删除末尾元素：O(1)。
- 删除中间（非末尾）元素：O(N)。
- 查：给定指定索引，查询索引对应的元素的值，时间复杂度 O(1)。
- 改：给定指定索引，修改索引对应的元素的值，时间复杂度 O(1)。
动态数组
刚才讲了静态数组的超能力和种种局限性，现在讲动态数组，动态数组是静态数组的强化版，也是我们在写算法题时最常用的数据结构之一。
首先，你不要以为动态数组可以解决静态数组在中间增删元素效率差的问题，不可能解决的。数组随机访问的超能力源于数组连续的内存空间，而连续的内存空间就不可避免地面对数据搬移和扩缩容的问题。
动态数组底层还是静态数组，只是自动帮我们进行数组空间的扩缩容，并把增删查改操作进行了封装，让我们使用起来更方便而已。
简单列举一下动态数组使用方法：
// 创建动态数组
// 不用显式指定数组大小，它会根据实际存储的元素数量自动扩缩容
vector<int> arr;
for (int i = 0; i < 10; i++) {
// 在末尾追加元素，时间复杂度 O(1)
arr.push_back(i);
}
// 在中间插入元素，时间复杂度 O(N)
// 在索引 2 的位置插入元素 666
arr.insert(arr.begin() + 2, 666);
// 在头部插入元素，时间复杂度 O(N)
arr.insert(arr.begin(), -1);
// 删除末尾元素，时间复杂度 O(1)
arr.pop_back();
// 删除中间元素，时间复杂度 O(N)
// 删除索引 2 的元素
arr.erase(arr.begin() + 2);
// 根据索引查询元素，时间复杂度 O(1)
int a = arr[0];
// 根据索引修改元素，时间复杂度 O(1)
arr[0] = 100;
// 根据元素值查找索引，时间复杂度 O(N)
int index = find(arr.begin(), arr.end(), 666) - arr.begin();