Course 01 · 基础算法

六件顺手工具
练到不用想

二分、排序、双指针、前缀和、高精度、模拟——它们不是「简单题」,而是后面所有算法题的地基。每一讲都有动画,也都有可以照着抄的题。

6个主题
60步可交互演示
6道配套例题
二分查找 · 找 56lo=0 hi=11
mid = —比较 0 次
01 / 二分查找

每次砍掉一半,4 次就找到

在 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 排除掉。
02 / 冒泡排序

相邻比较,把最大的「冒」到末尾

5 个数,一轮走下来最大的那个一定会浮到最右边。已经排好的尾巴会变成绿色——下一轮就不用再看它了。

→
注意「提前结束」那一轮。如果某一轮从头到尾一次都没交换,说明数组已经有序,可以直接 break。例子里的第 4 轮就是这样——这就是最好的情况 O(n) 从哪来的。
03 / 双指针

一头一尾,和大了就收右边

有序数组里找两个数加起来等于 21。和太小就把左指针右移,和太大就把右指针左移——每步都能确定地排除掉一个数。

✓
为什么可以放心移?数组是升序的。当 a[L] + a[R] < target 时,a[L] 配上任何比 a[R] 更小的数都只会更小,所以 a[L] 可以直接淘汰。「有序」是这个技巧成立的全部前提——乱序就得先排序,或者换哈希表。
04 / 前缀和

预处理一次,之后每次查询 O(1)

数组 [3,1,4,1,5,9],要反复问「第 2 到第 5 个加起来是多少」。先花 O(n) 建一张前缀和表,之后每个区间都是一次减法。

a
P
Σ
差分是它的镜像。如果题目是「给区间 [l,r] 整体加 v,最后输出整个数组」,那就用差分:d[l] += v; d[r+1] -= v,最后做一遍前缀和还原。区间修改+单点查询 和 单点修改+区间查询 是同一枚硬币的两面。
05 / 高精度

long long 装不下,就用字符串装

两个 20 位的整数相加,结果已经超出 long long 的上限(约 9.2×10¹⁸)。办法很朴素:像小学竖式一样,从个位开始一位位加,进位单独记。

A
B
=
!
三个必须检查的地方:① 最高位的进位别丢(if (carry) push_back(carry));② 两个数长度不同时,短的那个高位要补 0;③ 存的时候倒着存(下标 0 是个位),输出时再倒回来——正着存会让进位处理非常别扭。
06 / 模拟

不套算法,题目怎么说你就怎么做

「模拟」不是一种算法,而是照着题意把过程一步步走一遍。难点从来不是思路,而是边界:什么时候转向、什么时候停、下标越不越界。这里用 4×4 的螺旋矩阵演示。

方向 → 向右 已填 0 / 16
↻
模拟题的通用写法:把「方向」抽成两个数组 dr[] / dc[],撞墙或撞到自己已经走过的格子就 d = (d+1) % 4 右转。别写四个 if-else 分支——改起来痛苦,还容易漏掉某一个方向的边界。
07 / 总结

看到这几个词,就该想到这几招

基础算法不是背模板,是建立「题目里的某个词 → 某个动作」的条件反射。

01有序 / 找某个值 / 找边界二分查找 · O(log n)
02数据量小 / 要求稳定 / 手写排序冒泡排序 · O(n²)(快排 O(n log n))
03有序数组里的两数 / 三数 / 去重双指针 · O(n)
04区间求和 / 多次查询 / 子数组和前缀和 · 预处理 O(n),查询 O(1)
05数据范围超过 10¹⁸ / 求阶乘 / 大数运算高精度 · 按位模拟,O(位数)
06规则明确 / 让你按步骤走 / 网格题模拟 · 照做,注意边界