数组解题技巧

二分查找（Binary Search）

二分查找(Binary Search)算法，也叫折半查找算法。二分查找针对的是一个有序的数组，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。时间复杂度是O(logn)，一般用于对普通搜索方法的优化。

二分查找的适用场景一般满足以下几点：

有序的数组，需要利用下标随机访问元素，所以不能是链表等其他数据结构
数据量太小的时候不适合，顺序遍历就足够；数据量太大（比如超过 1GB）的时候也不合适，数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻，此时的内存压力比较大

排序算法

利用快速排序、归并排序、冒泡排序等排序算法，先将数组转化为有序数组，再按照题目要求获取结果。

相关题目：数组中的第 K 个最大元素(使用快速排序)、合并两个有序数组（合并排序）等。

双指针

对撞指针

指针 i 和 j 分别指向数组的第一个元素和最后一个元素，然后指针 i 不断向前，指针 j 不断递减，直到 i = j（具体的逻辑和操作视情况而定）

滑动窗口

定义左右指针left和right，选择下标在区间 [left, right] 的连续子数组作为窗口，窗口整体向一个方向滑动。滑动期间根据题目要求不断调整左右指针的位置，窗口所对应的子数组也随之变化，可以从中选择所需的子数组。

在题目中实现滑动窗口，需要确定如下几点：

窗口内是什么
窗口的起始和结束位置
窗口的移动规律

通过滑动窗口法，可以将一些需要使用嵌套 for 循环的题目，转化为单个 for 循环，减少了许多重复计算，将时间复杂度降为 O(n)。

警惕数组的访问越界问题

数组占用了一段连续的内存空间，我们可以通过指定数组下标来访问这块内存里的不同位置。但是，当下标超过了数组的下标范围时，访问到的内存，就不再是这个数组的内存，而是其它变量的内存了。在C语言中访问越界不会造成编译错误，但是可能导致出现一些莫名其妙的错误，debug 的难度非常大，或者程序突然崩溃。而且，很多计算机病毒也正是利用到了代码中的数组越界可以访问非法地址的漏洞，来攻击系统，所以写代码的时候一定要警惕数组越界。不同于 C 语言，Java 本身会做越界检查，比如下面这几行 Java 代码，就会抛出java.lang.ArrayIndexOutOfBoundsException。

int[] a = new int[3];
a[3] = 10;

容器能否完全替代数组

针对数组类型，很多语言都提供了容器类，比如 Java 中的ArrayList、C++ STL 中的vector。在项目开发中，什么时候适合用数组，什么时候适合用容器呢?

以 Java 为例，其中的容器类 ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外，它还有一个优势，就是支持动态扩容。数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组，当第 11 个数据需要存储到数组中时，我们就需要重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。如果使用ArrayList，我们就完全不需要关心底层的扩容逻辑，ArrayList已经帮我们实现好了。每次存储空间不够的时候，它都会将空间自动扩容为 1.5 倍大小。不过，这里需要注意一点，因为扩容操作涉及内存申请和数据搬移，是比较耗时的。所以，如果事先能确定需要存储的数据大小，最好在创建 ArrayList 的时候事先指定数据大小。比如我们要从数据库中取出 10000 条数据放入 ArrayList。我们看下面这几行代码，你会发现，相比之下，事先指定数据大小可以省掉很多次内存申请和数据搬移操作。

ArrayList<User> users = new ArrayList(10000);
for (int i = 0; i < 10000; ++i) {
  users.add(xxx);
}

数组适用的场景有：

Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组
如果数据大小事先已知，并且对数据的操作非常简单，用不到 A rrayList 提供的大部分方法，也可以直接使用数组
当要表示多维数组时，用数组往往会比容器更加直观

总的来说，对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一点点性能，完全不会影响到系统整体的性能。但如果是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

二分查找（Binary Search）​

排序算法​

双指针​

对撞指针​

滑动窗口​

警惕数组的访问越界问题​

容器能否完全替代数组​

参考资料​