less than 1 minute read

记录近期刷数组相关题目的思路和细节，方便日后复习。

1. 二分查找的核心思路与细节

二分法根据具体情况，核心是一套移动规则：

  1. 两个指针的起点终点
    这个本题很好确定，比如 l=0, r=n-1。

  2. 比较 target 和 (l+r)/2 时的处理原则
    • 在“大于、小于、相等”三种情况下，应当分别调整左右指针，注意细节。
    • 例：if (mid == target) return mid; else if (mid < target) l = mid + 1; else r = mid - 1;
  3. 需要当心的情况
    • 例如无法跳出循环。这里面主要的细节：
      • 整数除法是截断处理的，这对于升序数组的 l 跳转到 (l+r)/2 有影响，因此可以设置一个 Math.max 来匹配。
      • 对于 r 在 r l 不相等时无影响。
      • 当 r l 相等但对应的值不等于目标值时，需要要么设置相等时专门测试，不匹配目标值就返回 -1，要么假如 while 里包含相等，则设置让他们可以反超的条件，例如 Math.max。

In short，先设置好基本的起点终点和 while 条件，然后写好三种情况的 if else 框架，在里面填充内容时考虑好对所有情况的涉及和确保收敛即可。其他情况应该也是大同小异。建议一律自己从零开始手搓，然后面试前再带着理解记忆即可。

2. 原地操作与移除元素

重点是原地，也就是只能用几个单一变量和一个原始数组倒腾。因此，必须将结果直接存储到原先的数组里。由于每个元素都需要检查一遍，因此用左右两个指针往中间合并。

  • 需要小心的点有：
    • 什么时候加 k，不可以重复加 k 也不能漏加（所有的非 val 元素初次被探索到时 k++）；
    • 以及 l r 临近时，如何不造成 r 危险越界、如何保证可以正常跳出循环，等等。

我的办法是思考 l r 临近时左右元素分别是否是 val 来进行分类讨论检验算法，需要细致一点。

hh 没想到我的解法时间常数上的复杂度还占优势，另一种解法由于左右指针都从同一方向出发，直观上理解细节方便一些。

以后可以写完后观察一下，有没有变量之间有特定的联系（例如 l k 同初始值同增），这样可以在最后合并掉一些变量，减少内存消耗。但小心，不要把例如 l++;k++ 变成 l++;l++，这样 l 重复被处理了。如果后面只需要返回 k 而不必用到 k，就删掉 k 用 l 代替即可。

3. 细节与分支覆盖（移除元素/数组题通用）

  1. 仔细检查 if else 等涉及分支处的各种情况的重叠、是否覆盖完毕等细节
  2. 升序降序不要搞混
  3. 代入具体例子检查一下越界情况
  4. 眼睛看好一整行，不要自己截断只看到半侧
  5. 当心指针增减的顺序对不对

4. 有序数组的平方

随想录题解的优势：直接不需要确定分界点，从最大的平方入手，两个指针分别从首尾向中靠齐。关键：原数组的开头和结尾已经是各自的分界点了，可以利用之，修改返回数组的赋值顺序并留意一下指针相遇时的情况即可。已有的条件要充分利用好，节省资源～

挑战：可以用二分法代替 for 循环寻找正负数的分界吗？

5. 长度最小的子数组（滑动窗口/双指针）

此题可观察到数学证明在优化时间复杂度上的重要性：

  • 由于 a+b+c+d+e 符合，a+b+c+d 不符合，因此 b+c+d 一定不符合（均为正整数）。
  • 所以 r 指针不会回退，只会一直有移。此时再直接在 for 循环里遍历 l 指针的值即可保证处理了所有情况。

6. 螺旋矩阵（模拟/方向切换）

  1. 先 try 左，左不行往上，上不行往右，右不行往下
  2. 只要有一个方向行，就先走到底，防止中途由于缺乏界限错误走位
  3. 当心 while 死循环，i 等于 nn 后代表最后一个元素已植入数组，此时 i 不会再改变，因此循环终止条件应该为 i < nn，不可以加入等号

我认为的核心：

  1. 什么时候切换方向？当然是当前圈的边长填满后切换方向，一个画到一半的边长是没必要切换方向的。
  2. 方向按照什么顺序切换：顺时针
  3. 起始方向如何确定？我认为都可以，只要保证第一次按照可走优先级时第一个出来的是向右即可。虽然我先尝试的左，但先上或先右应该也可以。

有空可以看看更高效的写法，例如在 if else while 里优化，和看了一眼的别人题解里的取余选方向。

以上为数组相关题型的个人刷题思路与注意事项。持续补充中！

You May Also Enjoy