数组
学习数据结构与算法
数组是多个相同类型或者说相同大小数据的集合，它在内存中是连续存储，可以根据索引快速定位某个元素。数组有以下几个特点。
- 数组中的元素在内存中是连续存储。
- 数组长度在定义数组时指定，不可更改。
- 数组中的元素必须是相同类型。
- 可以通过数组+索引的方式快速定位某个元素。
数组的优点有访问快，直接通过索引访问，时间复杂度为O(1)，但是插入和删除的时间复杂为O(N)。
例如，数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]的存储结构如下：
关于数组的更多介绍可参考维基百科
注释索引
存储的值
内存地址
- 010x00
- 120x01
- 230x02
- 340x03
- 450x04
- 560x05
- 670x06
- 780x07
- 890x08
- 9100x09
对于数组，我们可以通过下标的方式获取指定元素，比如数组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等等。
通常数组下标是从0开始，但是也有一些编程语言并非如此。
注释1/**
2 * 自定义动态扩容数组，实现增删改查
3 */
4class ZXList<T> {
5
6 /**
7 * 方便测试，初始容量设置小一点
8 */
9 private static final int DEFAULT_CAPACITY = 2;
10 private int size;
11 private Object[] data;
12
13 public ZXList() {
14 data = new Object[DEFAULT_CAPACITY];
15 }
16
17 public int size() {
18 return size;
19 }
20
21 public void add(T value) {
22 if (size == data.length) {
23 Object[] newData = new Object[data.length * 2];
24 System.arraycopy(data, 0, newData, 0, data.length);
25 data = newData;
26 }
27 data[size++] = value;
28 }
29
30 public void remove(int index) {
31 if (index >= size || index < 0) {
32 throw new ArrayIndexOutOfBoundsException(index);
33 }
34 int sizeMoved = size - index - 1;
35 if (sizeMoved > 0) {
36 System.arraycopy(data, index + 1, data, index, sizeMoved);
37 }
38 data[size--] = null;
39 }
40
41 public void set(int index, T value) {
42 if (index >= size || index < 0) {
43 throw new ArrayIndexOutOfBoundsException(index);
44 }
45 data[index] = value;
46 }
47
48 @SuppressWarnings("unchecked")
49 public T get(int index) {
50 if (index >= size) {
51 throw new ArrayIndexOutOfBoundsException(index);
52 }
53 return (T) data[index];
54 }
55
56 @Override
57 public String toString() {
58 StringBuilder sb = new StringBuilder("[");
59 for (int i = 0; i < size; i++) {
60 sb.append(data[i]);
61 if (i != size - 1) {
62 sb.append(",");
63 } else {
64 sb.append("]");
65 }
66 }
67 return sb.toString();
68 }
69}
70
71public class Main {
72
73 public static void main(String[] args) {
74 ZXList<Integer> list = new ZXList<>();
75 for (int i = 0; i < 20; i++) {
76 list.add(i);
77 }
78 assert list.size() == 20;
79 list.remove(list.size() - 1);
80 assert list.size() == 19;
81 list.set(0, 99);
82 assert list.get(0) == 99;
83
84 System.out.println(list);
85 }
86}
87解决数组相关的算法问题常用的技巧有双指针、滑动窗口，以下是几道比较经典的题目。
颜色分类问题
给定一个包含红色、白色和蓝色，一共 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
- 仅存在一个有效答案
主要思路是，定义两个指针，从数组前后两端向中间移动，由于数组本身是升序排列，所以如果两个指针当前元素的和小于目标值，则前面的指针后移；如果大于目标值，则后面的指针往前移，直到两者相等。该题也可以用哈希表表的方式来解，但是这样就没有利用上数组本身是有序的条件，而且空间复杂度比双指针的解法要高一些。