代码随想录算法训练营第五天天| 总结数组专题

数组：二分查找、双指针（包括快慢指针）、滑动窗口、模拟
链表：双指针、三指针、虚拟头指针、复杂指针操作画图明确每一步（标好次序）

数组

代码随想录总结的很好，如下图。我再结合自己的一些理解总结一下

基础

定义：数组是存放在连续内存空间上的相同类型数据的集合。
特点：数组下标都是从0开始的数组内存空间的地址是连续的
vector和array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。
c++中二维数组在地址空间上是连续的。

双指针法：循环变量不变原则

重点：1、区间的定义——是左闭右闭还是左闭右开。右开还是右闭决定了right指向的值能否被访问。确定好right指向的值能否被访问，据此确定双指针初始值、循环条件、更新值。
2、mid = left + (right - left) / 2; //避免（left + right）溢出的问题

704.二分查找

只适用于有序序列

左闭右闭：

right=nums.size()-1；
while (left <= right)；
right=middle-1；left=middle+1；

左闭右开：

right=nums.size()；
while (left<right)；
right= middleleft=middle+1；

27.移除元素

快慢指针的思想是：快指针向前遍历数组，慢指针根据快指针的遍历结果来对数组进行更新。

for(fast; fast < nums.size(); fast++)
		{
            if(nums[fast] != val){
                //nums[slow] = nums[fast];
                //slow++;
                nums[slow++] = nums[fast];
            }
        }

977.有序数组的平方

相向指针：平方后，数组由两端向中间递减，是分为有序的两段，所以用双指针从两端开始比较得到从大到小的序列。

209.长度最小的子数组

滑动窗口思想：子序列的终止位置依次向后遍历，根据当前子序列和大小的情况，不断调节子序列的起始位置。即右进左出，右指针依次向前遍历数组，左指针根据右指针的遍历结果来对数组进行维护更新。

关键词：连续子数组=》子序列，应该想到滑动窗口。

59.螺旋矩阵II

明确模拟顺时针画矩阵的过程:填充上行从左到右，填充右列从上到下，填充下行从右到左，填充左列从下到上

关键： 1、坚持循环变量不变原则 2、更新每圈的初始位置和每圈的四条边长度

总结

有序：考虑二分、双指针
连续子数组、子序列：考虑滑动窗口
模拟：坚持循环变量不变原则，更新每圈的初始位置和每圈的四条边长度