数组理论基础

数组在内存中的存储方式：数组是存放在连续内存空间上的相同类型数据的集合。数组可以通过下标索引的方式获取到下标对应的数据。

注意：①.数组下标从零开始。②.数组内存空间的地址是连续的。

对于数组操作的特点：查找方便，增删繁琐。

注意：C++中vector和array的区别，vector的底层实现是array，严格来说vector是容器，而不是一个数组。

对于二维数组，其内存是否连续取决于使用的语言，如C++中其内存地址就是连续的。

704.二分查找

二分法的应用条件：①有序数组。②数组中没有重复元素。若存在重复元素，则可能导致返回的数组下标不唯一。

二分法区间：注意左闭右闭和左闭右开的区别。此处的右侧所谓的开或者闭指的是，考不考虑最右侧索引位置的数据。右闭指的是考虑区间中最右侧的元素，右开指的是不考虑最右侧的元素。所以右闭起始时，右侧索引为nums.length-1，右开起始时，右侧索引为nums.length。这也影响了整个循环执行的条件。

27.移除元素

暴力解法：两次遍历数组，第一次遍历统计所有不等于val的数字的个数，并使用变量count记录所有不等于val的数字的个数。第二次遍历将不等于val的数赋值给数组的前count个元素。这样做不会导致遗漏，因为遍历时count永远小于等于遍历使用的变量i。

双向双指针法：循环nums.length次，每次检查一个元素。首先判断末尾指针指向的元素是不是目标数据，如果是则将末尾指针前移一位。若未执行上述操作，则意味着末尾指针指向的元素不是目标值。之后可以判断起始指针指向的元素是不是目标值，如果是则将末尾指针指向的元素和起始指针指向的值互换位置，并让末尾指针前移一位。若起始指针指向的元素不是目标值，则起始指针后移一位。整体执行逻辑用一次循环即可实现，循环结束的条件是begin<=end。

977.有序数组的平方

可以考虑通过双指针的方法，新建一个和原数组大小相同的数组。且设置两个指针，一个指向数组的起始元素，一个指向数组的结束元素。之后比较这两个指针指向位置的值的平方的大小。把较大的一个插入新建数组可插入部分的末尾位置。而整体循环的条件是begin<=end。