二分、排序、双指针、前缀和、高精度、模拟——它们不是「简单题」,而是后面所有算法题的地基。每一讲都有动画,也都有可以照着抄的题。
在 12 个有序数字里找 56。线性扫描最坏要看 12 次,二分只需要 4 次——按「下一步」,看区间是怎么一刀刀砍下去的。
while (lo < hi) 和 lo <= hi 混着写;② mid = (lo+hi)/2 在 lo、hi 很大时溢出(改成 lo + (hi-lo)/2);③ 更新写成 lo = mid 而不是 lo = mid + 1,直接死循环。区间里没有目标时,必须把 mid 排除掉。5 个数,一轮走下来最大的那个一定会浮到最右边。已经排好的尾巴会变成绿色——下一轮就不用再看它了。
break。例子里的第 4 轮就是这样——这就是最好的情况 O(n) 从哪来的。有序数组里找两个数加起来等于 21。和太小就把左指针右移,和太大就把右指针左移——每步都能确定地排除掉一个数。
a[L] + a[R] < target 时,a[L] 配上任何比 a[R] 更小的数都只会更小,所以 a[L] 可以直接淘汰。「有序」是这个技巧成立的全部前提——乱序就得先排序,或者换哈希表。数组 [3,1,4,1,5,9],要反复问「第 2 到第 5 个加起来是多少」。先花 O(n) 建一张前缀和表,之后每个区间都是一次减法。
d[l] += v; d[r+1] -= v,最后做一遍前缀和还原。区间修改+单点查询 和 单点修改+区间查询 是同一枚硬币的两面。两个 20 位的整数相加,结果已经超出 long long 的上限(约 9.2×10¹⁸)。办法很朴素:像小学竖式一样,从个位开始一位位加,进位单独记。
if (carry) push_back(carry));② 两个数长度不同时,短的那个高位要补 0;③ 存的时候倒着存(下标 0 是个位),输出时再倒回来——正着存会让进位处理非常别扭。「模拟」不是一种算法,而是照着题意把过程一步步走一遍。难点从来不是思路,而是边界:什么时候转向、什么时候停、下标越不越界。这里用 4×4 的螺旋矩阵演示。
dr[] / dc[],撞墙或撞到自己已经走过的格子就 d = (d+1) % 4 右转。别写四个 if-else 分支——改起来痛苦,还容易漏掉某一个方向的边界。基础算法不是背模板,是建立「题目里的某个词 → 某个动作」的条件反射。