代码随想录——数组部分刷题总结篇
目录
数组基础知识
一维数组
二维数组
数组经典题目
二分法
双指针法
滑动窗口
模型行为
前缀和
数组基础知识
一维数组
数组是存放在连续内存空间上的相同类型数据的集合。数组的下标是从0开始的。访问数组时不要越界。在对数组进行删除或新增元素时要移动其他元素的地址。
二维数组
主要来回顾一下二维数组的内存分布,也是我们容易混淆的点。

这是栈上分配的,形式和C语言中的一样,内存空间是完全连续的,该行的首元素和前一行的末元素的内存地址也是挨着存储的。需要注意的是,此种定义二维数组的方式中行数和列数必须是常数,不能是变量。

动态分布的,是不连续的,可以看到该行的首元素与上一行的末元素并不是连存放在一起的,而每一行的元素的内存地址是连续的。
int** arr2 = new int*[n];
for(int i=0; i
{
arr2[i] = new int[m];
}
解释一下如上在堆区定义array的代码:
首先这是在堆上动态分布(可以用n和m,不像上一种方法,坚决不能使用变量定义大小),并不是在栈上静态分布。
先创建指针数组int** arr2 = new int*[n]; arr2现在指向的是一个包含n个指针的数组,也就是说这个数组里面放的都是指针,也就可以理解为什么arr2是int**类型。
接着for循环为每一行分配内存,arr2[i]访问第i个指针,第i个指针指向在堆区又分配的包含m个int类型的一个数组,也就是每个arr2[i]都指向一个包含有m个整数类型的数组。
其内存分布是:


每一行都是独立的vector对象,内存是不连续的,关于这种写法的解释在记录6中有详细的解释说明。 严格来讲vector并不是array,虽然vector的底层是array,但vector是容器并不是数组。数组与vector在内存、初始化和执行效率还是有区别的。
三种方法都可以用arr[i][j]来进行访问,在使用时没有明确要求可以优先使用vector,stl中有许多vector的内置函数及算法,十分便利。
数组经典题目
二分法
该方法时间复杂度为O(logn),比遍历查节省时间很多,一般题目中要求时间复杂度为O(logn)时已经提示要用二分查找法了。二分法一定要注意循环不变量原则,使用左闭右闭:
right = nums.size() - 1;
while(left <= right){ }
right = middle - 1;
left = middel + 1;
题目举例
双指针法
通过一个快指针和一个慢指针在一个for循环里面完成两个for循环的工作。此方法的时间复杂度为O(n),空间复杂度为O(1)。一定要注意两个指针分别指向的是什么才不容易出错,一般来说快指针是用来寻找新数组(最后想得到的数组)元素;慢指针是指向更新的新数组的位置。双指针的思想在很多题目都十分常见,需要熟练掌握。
题目举例1 题目举例2
滑动窗口
滑动窗口其实也是双指针的变种,该方法时间复杂度为O(n),空间复杂度为O(1)。同样需要注意的是窗口两端的指针分别指向的是什么,除此之外还需注意窗口如何变动的条件的设置,窗口内也就是两个指针所夹住的区间代表的是什么。
题目举例1 题目举例2
题目举例2中用到了map容器,是我掌握非常好的一道题目,并且有道推荐题目“76最小覆盖子串”没有练习,后续补上。
模型行为
就是单纯的模拟,没有涉及到什么算法,但是很考验对代码的掌控能力及我称之为找规律的能力,得通过题目描述和示例清楚是怎么样来实现的。很容易把代码写的非常冗余且没有章法。
题目举例
前缀和
是一个大大降低时间复杂度的思想方法,非常实用,对于思想实现上没有很大难度,但就是实际应用时不太能够想到使用这个方法。
题目举例







