前言

本文的刷题顺序依照代码随想录进行，因此题目板块的划分也和代码随想录一致。每个版块我会按照以下内容进行组织：

• 该类型题目的特征
• 时间复杂度
• 值得一讲的相关题目知识
  

  文章目录

  • • 前言
    • 正文
    • • 数组
      • • 二分查找
        • 移除元素 & 有序数组的平方 & 长度最小的子数组
        • 螺旋矩阵
        • 总结

正文

数组

二分查找

• 特征：有序数组中找特定组合的快速查询方法
• 时间复杂度：O(logn)O(logn)O(logn)
• 值得一讲的相关题目知识：
  • 对于求平方根的题目：#69 x的平方根和#367 有效的完全平方数
    • 如果是截取式返回，便可以将其转化成一个查找问题，采用二分法快速定位到应截取的整数平方根；也可以采用牛顿迭代法，xn+1=xn−f(xn)/f′(xn)x_{n+1}=x_n-f(x_n)/f'(x_n)xn+1​=xn​−f(xn​)/f′(xn​)，但需要注意的是，面对截取式返回而采用牛顿迭代法，必须保证f(x)的单调性，同时初始取值必须大于截取的整数平方根，否则可能出现1.99999被截取为1的情形（正确值应该是2）

移除元素 & 有序数组的平方 & 长度最小的子数组

• 特征
  • 要求只遍历一遍数组就解决问题，不要重复遍历
  • 要求原地操作，最好不使用新的空间来存储数组
• 时间复杂度：O(n)O(n)O(n)，空间复杂度：O(1)O(1)O(1)
• 值得一讲的相关题目知识：
  • 该类题目在只遍历一遍数组的限制下，核心要义就是使用双指针，通过指针的不同作用，来完成原地操作更新值的需求。
    • 比如#26 删除有序数组中的重复项和#283 移动零使用的快慢指针，快指针用来遍历数组，慢指针则用来指向更新位置
    • 或者#977 有序数组的平方中双指针分别指向首和尾，从首尾两个方向依序从大到小插入至新数组
    • 又如#209 长度最小的子数组，采用滑动窗口思想，双指针分别代表窗口的起始和终止位置，窗口内的累加和始终保持小于目标值的状态，每遇到一次大于等于情况发生，记录一次最小长度
    • 还有#76 最小覆盖子串，也是采用滑动窗口思想，窗口内始终保持小于覆盖目标字符串状态

螺旋矩阵

• 特征
  • 要求按照→↓←↑的顺序遍历二维数组（因为该顺序像螺旋一样，故得名）
• 时间复杂度：O(n2)O(n^2)O(n2)，空间复杂度：O(1)O(1)O(1)
• 我的解题思路：在这里，我对边界的设置与代码随想录的想法不同，左右视为列遍历，由column控制for循环上限；上下视为行遍历，由row控制for循环上限。每执行完一次列/行遍历，row/column减一上限。直至row或column其中一个为0。该方案的好处是完全不需要关心矩阵最后一行/列如何特殊处理，都是由一个统一原则控制，代码如下

总结

数组部分的困难题目主要体现在字符串的各种操作上，如#76 最小覆盖子串这种。这种类型虽然难，但我总结出了两条通用的技巧：

• 大多采用滑动窗口法，通过滑动窗口来保证一次遍历完成任务
• 记住ASCII码上限为128，可通过int[128]int[128]int[128]来表示所有ASCII的映射，比利用MapMapMap进行相关操作更加简洁

另外，数组结构在JavaJavaJava中作为以下类的底层实现：

• ArrayListArrayListArrayList：所以该类的删除操作时间复杂度为O(n)O(n)O(n)，这是在编程中经常被忽视的一点