数组

数组是多个相同类型或者说相同大小数据的集合，它在内存中是连续存储，可以根据索引快速定位某个元素。数组有以下几个特点。

1. 数组中的元素在内存中是连续存储。
2. 数组长度在定义数组时指定，不可更改。
3. 数组中的元素必须是相同类型。
4. 可以通过数组+索引的方式快速定位某个元素。

数组的优点有访问快，直接通过索引访问，时间复杂度为O(1)，但是插入和删除的时间复杂为O(N)。

例如，数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]的存储结构如下：

对于数组，我们可以通过下标的方式获取指定元素，比如数组array=[1,2,3,4,5,6,7,8,9,10]，可以通过array[7]来获取元素8，注意下标从0开始，同样也可以通过array[7]=0，这种方式来修改指定位置的元素。

从维度上来看，上面的array数组我们称之为一维数组，如果数组的元素也是一个数组，那么种数组就称为多维数组，比如

二维数组

[[1, 2, 3], [4, 5, 6]]

三维数组

[[[1, 2], [3, 4]], [[5, 6], [7, 8]]]

对于多维数组，我们同样可以通过下标的方式获取指定位置的元素，比如获取上面二维数组中的元素4，可以通过array[1][0]来获取。

数组是非常基础的数据结构，很多其它数据结构的底层数据存储方式都可以用数组来实现。比如说List，Map、Stack、Queue等等。

解决数组相关的算法问题常用的技巧有双指针、滑动窗口，以下是几道比较经典的题目。

颜色分类问题

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

示例 1：

输入：nums = [2,0,2,1,1,0] 
输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]

示例 3：

输入：nums = [0]
输出：[0]

示例 4：

输入：nums = [1]
输出：[1]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

这道题有很多种解法，最容易想到就是对数组进行排序，这里的元素只有三个，所以非常适合用计数排序。在特定的条件下，计数排序相对于比较类的排序算法效率要高很多，能达到线性级别时间复杂度O(N+K)。

使用双指针的解法，主要思路是，因为总共有红色（0）、白色（1）和蓝色（2）三种颜色，所以我们只需要将红色移动到数组前面部分，将蓝色移动到数组后面部分，剩下的白色自然就是数组中间，这样就将三种颜色按序排列好了。

两数之和 II - 输入有序数组

给定一个已按照升序排列的整数数组 numbers，请你从数组中找出两个数满足相加之和等于目标数target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers的下标从 1 开始计数，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

示例 1：

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

示例 2：

输入：numbers = [2,3,4], target = 6
输出：[1,3]

示例 3：

输入：numbers = [-1,0], target = -1
输出：[1,2]

提示：

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• numbers 按 递增顺序 排列
• -1000 <= target <= 1000
• 仅存在一个有效答案

主要思路是，定义两个指针，从数组前后两端向中间移动，由于数组本身是升序排列，所以如果两个指针当前元素的和小于目标值，则前面的指针后移；如果大于目标值，则后面的指针往前移，直到两者相等。该题也可以用哈希表表的方式来解，但是这样就没有利用上数组本身是有序的条件，而且空间复杂度比双指针的解法要高一些。