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/

总结