数组及二维数组

数组
数组指一组数据，用于储存多个相同类型的数据集合。内存中表示为若干个大小一致，类型一样，地址连续的存储空间。数组在堆内存中存储，由main函数在栈内存中开辟安放数组地址的空间，由于数组连续，所以只需将数组首地址值分配给main以引用变量。数组空间默认初始化值为0(堆内存中的数据都有默认初始化值)。访问数组元素需用到角标，操作数组各数据可以通过索引角标完成，角标=数组长度-1。数组中查找元素的时间复杂度为O(1)，计算一次即可得到元素，与元素的个数无关。数组长度一旦确定就无法改变。
数组创建
java语言使用new操作符创建数组。创建数组需要先声明变量，声明变量的语法为"数据类型[] 数组名"具体方法如下：
1、数据类型[] 数组名=new 数据类型[长度]
另外也可以直接将数组元素赋值给数组：
2、数据类型[] 数组名={元素1，元素2，元素3……元素(数组名).length}
也可以用new操作符将元素赋值给数组：
3、数据类型[] 数组名=new 数据类型[]{元素1，元素2，元素3……元素(数组名).length}
数组：遍历，扩容，排序
遍历：(查看数组中每一个元素)
for(int i=0；i<=数组名.length-1；i++)
扩容：(当数组容量不够时需要扩充容量存储新数据，缩容相反。基本思想增加/减少数组长度)
基本做法：建立一个新数组，长度为用户所需长度，"-“为缩容，”+"为扩容。将原数组元素复制放入新数组中，然后将原数组删除。
如：
int temp=arr[j]；
arr[j]=arr[j+a]；
arr[j+a]=temp；
或者：
int[] arr=new int[]；
int deltSize=a；//-缩 +扩
int[] newArr=new int[arr.length+deltSize]；
排序：(简单排序：){冒泡排序(1)、选择排序(2)、插入排序(3) }

1、比较相邻两个数据若后一个大于前一个则不需排序，若后一个小于前一个则交换位置。重复上述过程，每排完一轮，比较次数就减少一次。则需要进行N-1轮排序，第i轮排序需要的比较次数为N-i次。所以需要两层循环，第一层循环i表示排序的轮数，第二层循环j表示比较的次数。时间复杂度O(n*n)。

2、在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换。第二次遍历n-2个数，找到最小的数值与第二个元素交换。则第i次遍历，找到最小的数值与第i个元素交换，排序完成。时间复杂度O(n*n)。

3、将指针指向数组中某个元素a，设a左侧全部有序，将a抽离，依次与元素a位置之前的元素相比较。当遇到比它大的元素b时则将较大的元素b右移，将a放入b的初始位置，直至找到比a小的元素或a左侧元素都大于a时第一轮排序结束。此时a左侧元素都比a小，右侧都比a大。第二轮排序指针后移重复以上过程。每操作一轮左侧有序元素增加一个，右侧无序元素减少一个。所以需要两层循环，第一层循环从index开始遍历从角标为0的每一个元素，第二层循环从index-1开始向左遍历，将每一个元素与i处的元素比较，直到j处的元素小于i出的元素或角标已达到第一位0；遍历从i到j的每一个元素使其右移，最后将index处的元素放到空位处。时间复杂度O(nn)，但比冒泡排序和选择排序快。

这个题应用了二分查找的方法。定义i指针从角标0开始，定义j指针从角标.length-1开始。我们先用最小的数加上最大的数，如果和等于目标值则直接返回加和。如果加和小于目标值，则i++找角标1与j的加和，依次类推。如果加和大于目标值，则用i与j–求加和。若数组里所有加和与目标值不匹配则返回null。
二维数组
多维数组可以看成是数组的数组，像二维数组就是一个特殊的一维数组，其每一个元素都是一个一维数组。二维数组可以用：数据类型[][] 数组名=new 数据类型[长度1][长度2]来创建。设一个二维数组有m个一维数组，每个一维数组长度为n，如：int a[][]=new int[n][m]，则可以看作一个nm的矩阵。
经典二维数组：五子棋
运行如下：
判别五子棋结束条件：