数组理论基础
基本说明
Java数组的父类为Object，可以存储的数据类型有：基本数据类型、引用数据类型（对象）。数组有定长特性，长度一经定下不可修改。要求可变长度时可考虑集合等其他存储结构。它存储在Java虚拟机的堆内存中，用new来创建，是一串连续的内存地址。由于元素类型相同，因此占用内存空间一样。占用的内存大小已知，使得它可以根据起始位置与下标直接找到数据地址，查询快。如果在数组中增删数据，增删位置后面的数据都要向前或向后移动，增删慢。
操作方式
静态初始化（指定内容，长度等于内容个数）：int[] arr = new int[]{1,2,3,4,5};
动态初始化（指定长度，默认初始值由数组的字符类型而定）：int arr[] = new int[3];
利用索引访问，其数组范围皆为从0到数组名.length-1。遍历方式：for循环遍历、for each遍历（for增强）。两者的区别是遍历过程中的局部变量代表的含义，前者代表数组的元素下标，后者代表数组的具体内容。
常见API
Arrays.toString()：输出字符串、Arrays.asList()：将数组转为List、List.toArray()：将List转为数组。
简单题
[704]二分查找，[27]移除元素，[977]有序数组的平方。
都可使用双指针法解决，不再赘述。
中等题
[209]长度最小的子数组
题设：给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
思路：卡哥把这种方法叫做滑动窗口法，其实就是通过双指针的移动，确定子数组的开始与结束位置。如下图：
结束索引先开始移动，直至子数组和大于目标值，再移动起始索引，直至子数组和小于目标值，循环往复。
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int sum = 0;
int start = 0;
int length = Integer.MAX_VALUE;
for (int end = 0; end < nums.length; end++) {
sum += nums[end];
while (sum >= target) {
length = Math.min(length, end - start + 1);
sum -= nums[start++];
}
}
return length == Integer.MAX_VALUE ? 0 : length;
}
}
时间复杂度：O(n)，其中n是数组的长度。指针start和end最多各移动n次。
空间复杂度：O(1)。
[59]螺旋矩阵 II
题设：给你一个正整数 n ，生成一个包含 1 到 n² 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
思路：螺旋矩阵题需要考虑地比较细致，其核心为始终左闭右开。循环层数为矩阵行数/2，当行数为奇数时，要对矩阵中心值进行单独赋值。在每层循环中，模拟从左到右、从上到下、从右到左、从下到上四个遍历过程。
class Solution {
public int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int loop = 0;
int num = 1;
while (loop < n / 2) {
//从左到右
for (int i = loop; i < n - loop - 1; i++) {
res[loop][i] = num++;
}
//从上到下
for (int i = loop; i < n - loop - 1; i++) {
res[i][n - loop - 1] = num++;
}
//从右到左
for (int i = n - loop - 1; i > loop; i--) {
res[n - loop - 1][i] = num++;
}
//从下到上
for (int i = n - loop - 1; i > loop; i--) {
res[i][loop] = num++;
}
loop++;
}
if (n % 2 == 1) res[loop][loop] = num;
return res;
}
}
其中，起始值、索引值边界都可以用loop循环值来控制，只要坚持左闭右开的原则，细心即可。
时间复杂度：O(n²)，其中n是给定的正整数。矩阵的大小是n×n，需要填入矩阵中的每个元素。
空间复杂度：O(1)。除了返回的矩阵以外，空间复杂度是常数。
总结
