# 参考解 · lab 0009 · 一维数据的两种走法

**做完五个任务再打开这里。** 这里的五个 `.py` 与任务目录里的文件同名：
把它们拷进 `lab/0009-linear-structures-two-pointers/` 覆盖同名文件，再跑 `py run_tests.py`，
应当五个任务全过（本机实测一秒出头）。

参考解是自包含的：`tools.py` 与 `run_tests.py` 这里各有一份，拷过去直接就能跑。
`task2` / `task3` / `task4` / `task5` 会 `import` 前面任务的函数（`task3` 要用 `task1`、`task2` 的），
所以五个文件要**一起**拷，别只拷一个。

## 逐个任务看什么

| 任务 | 参考解里补上的关键几行 | 要看的现象 |
| --- | --- | --- |
| 1 · 暴力版 | 两层循环：`for l in range(n)` 里先 `s = 0`，再 `for r in range(l, n)` 边扩边 `s += a[r]` | 小数组 `[4, 0, 0, 4, 0]`、S=4 是 9；2000 个正数是 44；含负数的 300 个数是 106。它是后面两个版本的**参照** |
| 2 · 前缀和 | `pre = [0]` 后逐个 `pre.append(pre[-1] + x)`；`need = pre[r + 1] - S`；`seen = {0: 1}` | 表是 `[0, 4, 4, 4, 8, 8]`（长度 n+1、`pre[0]=0`）；含负数时**仍与暴力版一致**——它没有「元素必须为正」这条前提 |
| 3 · 双指针 | `while r < n and s < S:` 后 `s -= a[l]`；错版把条件改成 `while s < S:` | 全正数上与暴力一致（44）；含负数时给出 4、暴力给 106（**不一致**）；去掉 `r < n` 的错版在 `[1, 2]`、S=100 上报 `IndexError: list index out of range` |
| 4 · 对拍 | `return (count_brute(a, S), count_prefix(a, S), count_window(a, S))`；`find_counterexample` 里 `if w != b: return arr` | 小数组三版答案 `(9, 9, 4)`；第一个反例就是 `[4, 0, 0, 4, 0]`；**全正数上三版始终一致**；含负数上 `(106, 106, 4)` |
| 5 · 耗时对照 | `timed(count_brute, a, S)` 三行；`best_of_three` 里逐个与手上的最小值比 | 暴力那一列翻倍涨约 4 倍（本机实测 3.9–4.4），前缀和与双指针约 2 倍；同规模上暴力比双指针慢 400 倍以上 |

## 每个任务的「为什么」

- **任务 1**：两层循环的代价是常数乘以区间个数 $\frac{n(n+1)}{2}$，所以是 $O(n^2)$。这一版慢，
  但它是**唯一一个正确性一眼能看清**的版本：「和恰好等于 S」这个条件它一个区间都没漏。
  第 8 课说的「先把暴力写对」，用处就在这里——后面两个版本都要拿它对拍。
  写的时候 `r` 从 `l` 起（不是从 `0` 起），否则含重复与反向的区间会被数进来。
- **任务 2**：把「两个下标都要动」的问题，换成「只需要动一个下标」。区间和公式
  $\text{pre}[r+1] - \text{pre}[l]$ 里 $l$ 与 $r$ 地位一样，`pre[0] = 0` 这一位让
  $l = 0$ 与 $r = n-1$ 都不用特判。`seen = {0: 1}` 不能省：它的含义是「前缀和 0 已经出现过一次」，
  对应左端点 $l = 0$（区间从数组开头算起）；少了它，所有从开头开始的区间都会漏掉。
  每轮**先查后记**，写反了空区间会被算进来。这一版与元素正负、数组有没有序都无关。
- **任务 3**：双指针把 $O(n)$ 的额外空间也省掉了，但多了一条前提，而这条前提在题面上看不出来。
  「和小于 S 就把 r 往右移」之所以有效，是因为右边新加进来的元素让和**变大**；
  「和大于 S 就把 l 往右移」之所以有效，是因为左边丢掉的元素让和**变小**。
  元素是全为正数时两条恒成立；出现 0 或负数，加进去和不变（或变小），这套规则就不再逼近 S。
  更直接的一条在下标上：`l` 只能往右走，被它丢在身后的位置**再也回不来**，
  而某些答案的左端点恰恰在那里——这就是「右指针只加不减导致漏解」。
- **任务 4**：对拍是最省力的查错手段。三个版本答案不一致时，正确的做法是**拿暴力版当基准**
  去查另外两个，而不是「三个里挑两个一致的」——后者在双指针「有时对、有时错」时会直接判错方向。
  小数组上让两版分岔的 S 有 3 个，其中 S = 4 是双指针**少算**（4 对 9）、S = 0 是**多算**（5 对 4）——
  这类版本比稳定的错版更难查，因为样例上跑出来经常是对的。
- **任务 5**：计时口径与第 3 课一致（前后各取一次 `perf_counter` 相减，中间不夹别的代码），
  取三次里最小值是为了躲开系统调度带来的偏大值。要看的**不是秒数绝对值**（换台机器就变），
  而是两条趋势：暴力那一列**翻倍涨四倍**（$O(n^2)$ 的样子），两个线性版**翻倍涨两倍**（$O(n)$ 的样子）。
  同规模上暴力与双指针差两个数量级以上，这个差距全部来自走法的改变——
  三个版本都是普通写法，没有谁写得更紧凑。

## 常见错法（对照自己的写法）

- **`r` 从 `0` 起**：每个区间会被数到好几遍，小数组打出的不是 9。要写 `for r in range(l, n)`。
- **忘了 `s = 0` 要写在外层循环里**：`s` 会被上一个左端点的累加带着走，答案偏大。
  它的位置在 `for l` 里、`for r` 外。
- **`build_pre` 里写成 `pre = []`**：表长变成 n、`pre[0]` 是 `a[0]`，就少了「还没开始累加」的那一位，
  `pre[r+1] - pre[l]` 整套下标都要跟着改。这是本课最常踩的一处：**表长永远是 n + 1**。
- **`seen = {}` 而不是 `{0: 1}`**：所有从数组开头算起的区间都漏掉，答案偏小。
- **先记后查**：写成先 `seen[...] += 1` 再 `count += seen.get(need, 0)`，空区间会被算进来。
- **双指针漏了 `r < n`**：数组末尾那两个数、S 又大时，`r` 会一路加上去，
  `a[r]` 报 `IndexError: list index out of range`。任务 3 的 TODO 2 就是让你亲眼复现这个报错。
- **双指针漏了末尾的 `s -= a[l]`**：窗口只涨不缩，等于每轮都在同一个起点上扩。
- **以为双指针「优化过所以更好」**：它在元素有 0 或负数时是**错的**，不是慢。
  判断只有一句：加一个元素、减一个元素之后，我关心的那个量会不会往回走。
- **计时把三个版本混在一起量**：`time_three` 要三次 `timed`、三次相减，
  不能一次 `start` 一次 `end` 把三个函数包在一起——那样量到的是总时间，看不出差距。
- **硬凑 `print` 后的数字**：判分读的就是那些行，硬凑等于没做。
  改完先自己跑 `py <任务文件>.py` 对一遍，再跑 `py run_tests.py`。

## 做完之后用一句话回答

双指针那三个前提（元素全为正数、数组有序、题目问「和恰好等于 S」而不是「和不大于 S」）里，
哪一个在这道题上不成立？说清「哪一步调整失效了」，就算这一课练到位了。