【理论】数组

数组概念

数组是存放在连续内存空间上的相同类型数据的集合。

数组可以方便的通过下标索引的方式获取到下标对应的数据。

举一个字符数组的例子，如图所示：

需要两点注意的是

• 数组下标都是从0开始的。
• 数组内存空间的地址是连续的

因为数组在内存空间的地址是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址。

例如删除下标为3的元素，需要对下标为3的元素后面的所有元素都要做移动操作，如图所示：

而且大家如果使用C++的话，要注意vector 和 array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。

数组的元素是不能删的，只能覆盖。

二维数组

那么二维数组在内存的空间地址是连续的么？

我们来举一个Java的例子，例如： int[][] rating = new int[3][4]; ， 这个二维数组在内存空间可不是一个 3*4 的连续地址空间

看了下图，就应该明白了：

所以Java的二维数组在内存中不是 3*4 的连续地址空间，而是四条连续的地址空间组成

数组经典题目

二分法

解法：循环不变量

在循环中坚持对区间的定义，才能清楚的把握循环中的各种细节。

• 暴力法时间复杂度：O（n）
• 二分法时间复杂度：O（logn）

双指针法

解法：快慢指针法

通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

• 暴力解法时间复杂度：O(n^2)
• 双指针时间复杂度：O(n)

滑动窗口

解法：

理解滑动窗口如何移动 窗口起始位置，达到动态更新窗口大小的，从而得出长度最小的符合条件的长度。

根据当前子序列和大小的情况，不断调节子序列的起始位置。

• 暴力解法时间复杂度：O(n^2)
• 滑动窗口时间复杂度：O(n)

模拟题

解法：循环不变量

真正解决题目的代码都是简洁的，或者有原则性的

前缀和

解法：一维：l~r等价于s[r]-s[l-1]；二维：s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+x;

总结