代码随想录二刷 ｜ 数组 ｜ 总结篇

基础知识

定义：数组是存放在连续内存空间上的相同类型数据的集合

特点：

• 数组下标从 0 开始
• 数组内存空间的地址是连续的

vector 和 array 的区别：vector底层实现是 array，严格来讲 vector 是容器不是数组

C++中二维数组在地址空间上是连续的

二分查找

注意循环不变量原则

• 左闭右闭
  • right = nums.size() - 1
  • while (left <= right)
  • right = middle - 1;
  • left = middle + 1;
• 左闭右开
  • right = nums.size()
  • while (left < right)
  • right = middle
  • left = middle + 1

移除元素

双指针法：通过一个快指针和慢指针在一个 for 循环下完成两个 for 循环的工作

相向双指针：a指针从左到右，b指针从右到左，a指针找等于目标值的位置，b指针找不等于目标值的位置，然后每次找到一个用b指针覆盖a指针

有序数组的平方

双指针法：a指针从左到右，b指针从右到左，两个指针每次比较平方的大小，大的存入结果数组并移动指针，小的停在原地

时间复杂度：O(n)
空间复杂度：O(n)

长度最小的数组

滑动窗口：双指针的变种，这一题需要两个指针都能固定住且一个指针固定，另一个可以连续变化

外层for循环更改一个指针，内层用while循环连续更新另一个指针。

时间复杂度：O(n)
空间复杂度：O(1)

最小覆盖子串

创建一个unorder_map 维护目标字符串各字母出现的次数。

再创建一个unordered_map记录遍历过中目标字符串各个字母出现的次数，方便修改并且不用在滑动窗口变化时对上一个 map 进行修改

遍历过程中如果达到目标字符串次数就收缩窗口左边界，并且记录窗口起点，当收缩的窗口不能完全覆盖目标字符串就扩展窗口右边界，直到再次能完全覆盖

当右窗口到达终点，左边界收缩完成，将此时的起点用于分割字符串

螺旋数组

对于正方形的二维数组只需要考虑转多少圈以及最后中间是否只剩一个值，如果剩一个值需要再转完圈后单独加中间的值。另外转圈过程要保持循环不变量的原则。

对于矩形二维数组编程一维数组的情况，需要在转完圈后单独考虑最内圈剩下的一行或者一列。

总结参考录友@海螺人的思维导图 代码随想录