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

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

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

二分查找：

        算法的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当看到题目描述满足如上条件的时候，可要想一想是不是可以用二分法了。

        写二分法经常写乱，主要是因为对区间的定义没有想清楚，区间的定义就是不变量。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

        循环不变量：在while或者for过程中，很多都是重复执行，比如while和for里面的判断。很多情况里面的判断条件都是不等式，那这个循环不变量就包括区间。比如[,)区间就包括右边界，那每次判断都不包括右边界。如果右边界是需要加进去判断的值，这样写就不可以。

java版二分法写法（左闭右闭）：

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length - 1;//right是包含的nums最后一个数值
        while (left <= right) {//因为包含右边界，所以右边界是需要进行判断的，所以判断条件是<=
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;//需要+1，中间值肯定不满足条件，所以已经判断过了
            else if (nums[mid] > target)
                right = mid - 1;
        }
        return -1;
    }
}

删除数组元素（双指针）

可能说了，多余的元素，删掉不就得了。

要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。

双指针的形式：1.fast指针比slow指针步数跨度大，例如slow一次1步，fast一次2步；解决链表环形入口

2.指针A和指针B从两边向中间移动，例如下面例题带负数有序平方排序问题

3.fast在slow前面一步，fast按一步步走，slow满足条件再走，相当远fast是一个探路的。slow做修改。比较有特点的就是删除数组元素

还有很多形式，还是需要更多的练习。

class Solution {
    public int removeElement(int[] nums, int val) {

        // 快慢指针
        int fastIndex = 0;
        int slowIndex;
        for (slowIndex = 0; fastIndex < nums.length; fastIndex++) {
            if (nums[fastIndex] != val) {
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
        }
        return slowIndex;

    }
}

带有负数有序平方再排序

一般整体排的话用快排，再平方时间复杂度n×log(n) + n

但是通过双指针，用过再在内存上开辟个存储地方，从两头比较A和B的平方大小，大的那个放到新开辟的地方，同时让指针大的那个移动，在比较，循环一边就可以做到了，时间复杂度就是n.

class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int k = A.size() - 1;
        vector<int> result(A.size(), 0);
        for (int i = 0, j = A.size() - 1; i <= j;) { // 注意这里要i <= j，因为最后要处理两个元素
            if (A[i] * A[i] < A[j] * A[j])  {
                result[k--] = A[j] * A[j];
                j--;
            }
            else {
                result[k--] = A[i] * A[i];
                i++;
            }
        }
        return result;
    }
};

螺旋矩阵一写就废：

要时刻记得循环不变原则，按正方形的圈来，每次都是左闭右开。每次需要更新初始节点，和长度n

模拟顺时针画矩阵的过程:

• 填充上行从左到右
• 填充右列从上到下
• 填充下行从右到左
• 填充左列从下到上

由外向内一圈一圈这么画下去。

可以发现这里的边界条件非常多，在一个循环中，如此多的边界条件，如果不按照固定规则来遍历，那就是一进循环深似海，从此offer是路人。

这里一圈下来，我们要画每四条边，这四条边怎么画，每画一条边都要坚持一致的左闭右开，或者左开又闭的原则，这样这一圈才能按照统一的规则画下来。

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] arr = new int[n][n];
        int t = 1,mid = 0;
        int loop = n/2;
        int counter = 1;
        if(n%2 == 1){
            arr[n/2][n/2] =n*n;
        }
        int startx = 0 ,starty = 0;
        while(loop > 0){
            for(int x =startx,y = starty;y<starty + n-1;y++){
                arr[x][y]=counter;
                counter++;
            }
            for(int y = starty + n - 1,x=startx;x <starty + n-1;x++){
                arr[x][y]=counter;
                counter++;   
            }
            for(int x = startx + n - 1,y=starty + n-1;y>startx;y--){
                arr[x][y]=counter;
                counter++; 
            }
            for(int y = starty,x=startx + n-1;x>startx;x--){
                arr[x][y]=counter;
                counter++; 
            }
            startx++;  starty++;
            loop--;n=n-2;
        }
    return arr;

    }
}

59. 螺旋矩阵 II