思考：为什么数组要从 0 开始编号，而不是从 1 开始呢？

数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据**

1. 线性表（Linear List）

线性表就是数据排成一条线一样的结构，每个线性表上的数据最多只有前后两个方向。除了数组，链表、队列、栈也是线性表结构。

对应的概念是非线性表，如二叉树、堆、图等，数据之间并不是简单的前后关系。

2. 连续的内存空间和相同类型的数据

这两点让数组有了一个重要的特性：「随机访问」。

• 优势： 下标随机访问（⚠️而非查找操作）的时间复杂度是O(1)
• 劣势：删除、插入等操作，为了保证连续性而变得低效

a[i]_address = base_address + i * data_type_size

数组为了保持内存数据的连续性，会导致插入、删除的操作比较低效。

• 插入操作：
  • 有序
  • 无序
• 删除操作：
  • 标记->需时一次批量删除

• 容器的优势：
  • 封装许多数组操作细节
  • 支持动态扩容

对于业务开发，直接用容器就足够了；

对于底层开发，性能需要优化到极致，就要考虑优选数组了。

「下标」的定义是「偏移」

以下是从 0 开始：

a[i]_address = base_address + i * data_type_size

以下是从 1 开始：

a[k]_address = base_address + (k-1)*type_size

• 从 1 开始，每次随机访问数组元素时都多了一次减法运算。
• 最主要原因可能还是历史原因

• 初始化

• 获取长度

• 「随机访问」根据索引获取元素

• 元素遍历

• 修改元素

• 排序

• 做好初始定义

做数组类算法问题的时候，常常需要定义一个变量，明确该变量的定义，并且在整个算法逻辑中，不停地维护住这个变量的定义，特别注意初始值和边界的问题。

• 运用基础算法思想

典型的排序算法思想、二分查找思想在数组中应用非常广泛

• 双索引技巧 - 对撞指针

对撞指针：指针 i 和 j 分别指向数组的第一个元素和最后一个元素，然后指针 i 不断向前，指针 j 不断递减向后，直到 i = j。

• 双索引技巧 - 滑动窗口

一些题目利用「滑动窗口」方法，可以将时间复杂度控制在 O(n) 级别。定义好滑动窗口，明确表达的意思，并考虑边界与初始值。