今天看卡哥代码随想录第一课 数组理论基础
- array在内存上是连续的,包括二维数组
- array是容器vector的底层实现
刷题:
常见的二分法
容易写错的是两个地方:一是条件判断:while(left < right) 二是right = middle - 1还是right = midddle (left一直都是 left = middle + 1, 因为我们一般没有定义左开右闭区间)
判断方法:
要是我们定义我们的target搜索空间为左闭右闭区间:就用while(left <= right) 和 right = middle - 1
要是我们定义我们的target搜索空间为左闭右开区间:就用while(left < right) 和 right = middle
数组元素删除
c++里的vector erase的时间复杂度为O(n)。
快慢指针可以解决,使用慢指针覆盖(没有删除操作)
有序含负数数组 -> 有序平方数组
指针从两头开始