1、概念

数组是存放在连续空间上的相同类型的数据集合。
特点：
1、数组下标都是从0开始的；
2、数组内存空间的地址是连续的。

C++,要注意vector和array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。
C++中二位数组在地址空间是连续的。测试代码：

void test_arr() {
    int array[2][3] = {
  {0, 1, 2},
  {3, 4, 5}
    };
    cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;
    cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
}

int main() {
    test_arr();
}

2、二分查找 主要理解区间定义，对循环条件的影响

特点：前提是有序数组，而且没有无重复元素
题目：https://leetcode-cn.com/problems/binary-search/.
首位置 末尾位置，中间位置。
当中间位置的数字>目标数字 末尾位置挪移到中间位置
当中间位置的数字<目标数字 首位置挪移到中间位置
中间位置<0 中间位置>末尾位置 非法边界。
第一种写法 [left,right]
第二种写法[left,right)

int search(int* nums, int numsSize, int target){
    int left = 0;
    int right = numsSize - 1; 

    while (left <= right){
        int middle = left + ((right - left) / 2); //防止溢出  防止什么溢出

        if (nums[middle] > target) {
            right = middle - 1;
        } else if (nums[middle] < target){
            left = middle + 1;
        }
        else{
            return middle;
        }
    }

    return -1;

}

3、移除元素

题目：https://leetcode-cn.com/problems/remove-element/
第一种：暴力实现
第二种：双指针：一个快指针，一个慢指针
快指针是寻找这个新数组里所需要的元素（除去所需要删除目标元素的元素）
新数组的更新的位置就是slow。
在快指针获取到的值赋给慢指针就可以了。

int removeElement(int* nums, int numsSize, int val){
    int slowIndex = 0;
    for (int fastIndex = 0; fastIndex < numsSize; fastIndex++){
        if (val != nums[fastIndex]){
            nums[slowIndex++] = nums[fastIndex];
        }
    }

    return slowIndex;
};

类似题目：
26 删除排序数组中的重复项
283 移动零
844 比较含退格的字符串

有序数组的平方

题目：https://leetcode-cn.com/problems/squares-of-a-sorted-array/
第一种方法：暴力解法 每个数平方之后，排序即可
第二种方法：双指针法
考虑题目的特征：有序数组，那么数组的平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。
此时可以考虑双指针法，i指向起始位置，j指向终止位置
定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。
怎么想到定义了一个新数组？因为数组的元素已经改变，不仅是位置的改变还有内容的改变。

#include <stdio.h>
#include <math.h>

int main()
{
    int originalArr[5] = {-3,-2,4,5,6};
    int newArr[5] = {0};
    int i = 0;
    int j = 4;
    int k = 4;

    /*
    首先比较初始元素的平方和末尾元素的平方大小
    其次，将较大的一方放入新数组的末尾位置，并移动i或j的位置。

    循环结束的条件，i <= j
    */
   while (i <= j)
   {
        if (pow(originalArr[i],2) > pow(originalArr[j],2))
        {
            newArr[k] = pow(originalArr[i],2); 
            i++;
            k--;
        }
        else
        {
            newArr[k] = pow(originalArr[j],2);
            j--;
            k--;
        }
   }

   for (int i = 0; i < 5; i++)
   {
        printf("%d ",newArr[i]);
   }
   

   return 0;

}

长度最小的子数组（滑动窗口）

螺旋矩阵

题目：https://leetcode-cn.com/problems/spiral-matrix-ii/

总结