# 0011 · 双指针：两个下标的配合 · 参考解

这一课只有一个动作：**两个下标怎么配合着走**。五个任务把它拆成五种配合方式。

```text
两数之和      ──对撞（从两端往中间收）──▶ 每轮丢掉一格候选
if 与 while   ──同一个走法、只差一处关键字──▶ 漏解与不漏解的分界
原地去重      ──快慢（一个读一个写）──▶ 写出位置划出有效段
回文判定      ──对撞（两端同时往中间收）──▶ 一趟同时给出结论与错位位置
合并有序数组  ──从后往前写──▶ 空位刚好装得下多出来的元素
```

| 任务 | 文件 | 要交的东西 |
| --- | --- | --- |
| 1 · 两数之和 | `task1_two_sum_sorted.py` | `two_sum_brute` / `two_sum_sorted` / 每档的轮数 |
| 2 · if 与 while | `task2_if_vs_while.py` | `two_sum_if`（故意漏解）/ `two_sum_while` |
| 3 · 原地去重 | `task3_dedup_inplace.py` | 正确版 / 删掉 `slow += 1` 的错版 |
| 4 · 回文判定 | `task4_palindrome.py` | `is_palindrome` / `first_mismatch` |
| 5 · 合并有序数组 | `task5_merge_sorted.py` | 新列表版 / 原地版 / 取前 k 项 |

把这一份里的文件拷进你的任务目录就能直接跑（`tools.py`、`run_tests.py` 与 `probes/` 两侧内容完全相同）：

```text
py run_tests.py        # 在 lab/solutions/0011-two-pointers-applications/ 目录里直接跑
```

参考解的判分结果：**71 PASS / 0 FAIL、退出码 0**。留白版是 **13 PASS / 58 FAIL、退出码 1**，
58 条 FAIL 每条都点名要改的 TODO。

## 逐题：为什么这么写

### 任务 1 · 对撞指针凭什么能丢掉一格

两数之和的暴力版是两层循环，代价 $O(n^2)$。对撞版把两个下标放在两端，每轮比较
`a[l] + a[r]` 与目标值，按结果丢掉一格。三条规则：

| 比较结果 | 动作 | 丢掉的那一格为什么可以丢 |
| --- | --- | --- |
| `== target` | `return (l, r)` | 什么都没有丢，已经找到 |
| `< target` | `l += 1` | 和偏小时，`a[l]` 与 `[l, r]` 里**任何**元素的和都不超过 `a[l] + a[r]`，所以 `a[l]` 配不出答案 |
| `> target` | `r -= 1` | 和偏大时对称，`a[r]` 配谁都太大 |

后两条**靠「有序」这条前提才成立**。一轮丢掉一格，一共丢掉 $n-1$ 格，所以轮数正好是
$n - 1$：

| 规模 n | 轮数 | 每轮丢掉的格数 |
| --- | --- | --- |
| 20 | 19 | 1 |
| 200 | 199 | 1 |
| 2000 | 1999 | 1 |
| 8000 | 7999 | 1 |

判分读的就是 `每档的轮数` 那一行，期望 `[19, 199, 1999, 7999]`。

**这一题有一处判分特意放宽了**：`[0, 0, 0]` 目标和 0 时，`(0, 1)`、`(0, 2)`、`(1, 2)`
都是合法答案。对撞版从两端出发，第一次比较就命中 `(0, 2)`；两层循环从左往右扫，
先命中 `(0, 1)`。**两个都对**，所以判分只检查「交回的那一对满足 `i < j` 且
`a[i] + a[j] == target`」，不写死是哪一对。

### 任务 2 · 一处关键字决定漏不漏解

`two_sum_if` 与 `two_sum_while` 的差别只有一处：

```text
if 版     外层 for l，和偏大时 right -= 1 只收一格
while 版  外层 for l，和偏大时一直收，直到不再偏大
```

`if` 版漏解的原因值得单独说清楚：**和偏大时它只收一格，而下一轮 `for` 已经把 `l`
交给了下一个值**——于是「同一个 `l`、更小的 `r`」那些组合再也没被检查。

在课件那组数据 `[1, 4, 5, 9, 11]`、目标 10 上，`if` 版的逐轮状态是：

| 轮 | l | r | a[l] + a[r] | 判断 |
| --- | --- | --- | --- | --- |
| 1 | 0 | 4 | 12 | 偏大 → r 收到 3 |
| 2 | 1 | 3 | 13 | 偏大 → r 收到 2 |
| 3 | 2 | 2 | — | l 与 r 相遇，退出 |

它在第 2 轮把 `r` 收到 2，而答案 `(0, 3)` 需要 `l = 0`——**可是 `l` 已经走到 1 了**。

**五组数据里它只漏这一组**（判分期望 `if 版漏解组数 = 1`）。其余四组要么第一次比较就
命中，要么和一直偏小、`r` 根本不用动。所以这条判据的意思不是「`if` 版处处都错」，
而是**它错在一个特定的输入形状上**——这正是这类 bug 危险的地方。

`while` 版的内层条件带着 `l < r`：

```text
while l < r and a[l] + a[r] > target:
    r -= 1
```

那个 `l < r` 不能省：它保证 `r` 不会收到 `l` 左边去。两个下标交错之后再比较，
得到的一对次序就反了。

### 任务 3 · 快慢指针：一个读、一个写

原地去重里，两个下标的分工完全不同：

| 下标 | 职责 | 不变式 |
| --- | --- | --- |
| `fast` | 读，从 0 走到末尾 | 它左边的每个元素都已看过 |
| `slow` | 写，只在写入新值时前移 | `a[:slow]` 是已经去重好的那一段 |

**`a[:slow]` 始终是答案的前缀**——这就是「不变式」。每次 `fast` 读到一个与 `a[slow-1]`
不同的值，就把它写到 `a[slow]` 再让 `slow` 前移。

错版只删掉一行 `slow += 1`，后果是**两个错互相解释**：

| | 个数 | 整个数组 |
| --- | --- | --- |
| 正确版 | 4 | `[1, 2, 3, 5, 3, 5]` |
| 错版（删掉 `slow += 1`） | 1 | `[5, 1, 2, 3, 3, 5]` |

`[1, 1, 2, 3, 3, 5]` 上，错版把每个新值都写到同一个位置 `a[0]`，最后一次写入的是 5，
于是数组变成 `[5, ...]`；而它交回的个数 1 说的正是「我只有一个有效元素」——**它自己
是自洽的，只是答错了**。

判分这里用的是**探针**：交回的是个数，内容在数组里，所以另起一个进程拿判分自己的数据
试 `(k, a[:k])` 两段。

### 任务 4 · 回文判定：一趟同时给出两件事

`is_palindrome` 和 `first_mismatch` 是**同一趟走法**——两个下标从两端同时往中间收，
只差在「不相等时」交出什么：

| 函数 | 不相等时 | 全部相等时 |
| --- | --- | --- |
| `is_palindrome` | `False` | `True` |
| `first_mismatch` | 那一对下标 `(i, j)` | `-1` |

有两处关键：

- **相等时两个指针都要动。** 只动一个会原地打转：`l` 不动、`r` 一直左移，
  永远收不到中间，最后错位位置也报错。
- **判定与定位必须是同一趟。** 写成两个独立函数就会漂移——判据说的是「同一次比较
  里既得出 `False` 又得出那一对下标」。

十组用例里有三组值得盯：

| 输入 | 判定 | 第一处错位 | 为什么值得盯 |
| --- | --- | --- | --- |
| `'abcabc'` | `False` | `(0, 5)` | `a` 与 `c` 一比就错，第 0 位就对不上 |
| `[1, 2, 2, 3]` | `False` | `(0, 3)` | 列表版与字符串版走的是同一套下标逻辑 |
| `'abca'` | `False` | `(1, 2)` | 收了一格之后才错——**不是 `(0, 3)`** |

最后一行是判分特意加的对照：`'abca'` 的首尾都是 `a`、相等，两个指针各动一格之后
才在 `b` 与 `c` 上分开。凡是「首尾一比就报错」的写法都会在这里交出 `(0, 3)`。

### 任务 5 · 合并有序数组：为什么从后往前

`a` 的前 `m` 项和 `b` 的有效部分都有序，`a` 的后半段是空位，空位刚好够装下 `b`。
从前往后写会**覆盖掉 `a` 里还没读的元素**；从后往前写则总是写到空位上。

| 版本 | 起点 | 关键点 |
| --- | --- | --- |
| 新列表版 | 两个指针从头开始 | 两个收尾 `while` 都要写，漏一个会丢尾巴 |
| 原地版 | `p = m - 1`、`q = len(b) - 1`、`w = 末尾` | 谁大就把谁写进 `w`，然后 `w -= 1` |
| 取前 k 项 | 合并到取满 k 项为止 | `k` 大于总长时把能给的都给出来 |

原地版有一处容易漏：**循环条件是 `q >= 0`，不是 `p >= 0`**。`b` 用完就结束了——
`a` 里剩下的那些本来就在正确位置上，不用再搬。

判分对原地版用的是探针，因为原地改写的返回值不足以判断结果：探针拿判分自己的数据
直接检查数组内容，四组覆盖 `b` 比空位短、正好、末尾两格等等情形。

## 常见错法（判分逐条盯着）

| 错法 | 会看到什么 |
| --- | --- |
| 对撞指针每轮同时动两个下标 | 会跳过候选，答案直接交成 `None` |
| 循环条件写成 `l <= r` | `l` 与 `r` 相等时还在比较，可能交回 `(l, l)` 这种同一个位置用两次的对 |
| 和偏小时忘了 `l += 1` | 死循环——两个指针都不动 |
| 快慢指针忘了 `slow += 1` | 个数交回 1，数组内容被写花成 `[5, ...]` |
| 回文判定里只动一个指针 | 原地打转，或者错位位置报到数组另一头 |
| 原地合并从前往后写 | 覆盖掉 `a` 里还没读的元素 |
| 原地合并的收尾条件写成 `p >= 0` | `b` 用完还在搬，把 `a` 的内容又写乱 |
| 取前 k 项没处理 `k` 大于总长 | 下标越界，或者少给元素 |

## 判分在读什么

- **五个任务各起一个进程跑**，只看 stdout 里的固定格式行，**不 import 你的代码**——
  所以「只写 `print` 不写实现」拿不到分。
- **对撞靠对拍验**：任务 1 的对撞版在课件那三组、四组边界、四组规模上都与两层循环的
  基准一致；任务 2 的 `while` 版在五组数据上与基准一致。
- **「两数之和」只判交回的对合不合法，不写死是哪一对**（见任务 1 那一节）。
- **原地改写靠探针验**：`probes/probe_task1.py`、`probe_task3.py`、`probe_task5.py`
  另起进程 import 你的函数，拿判分自己砌的数据重算期望值逐字对照。
- **一条耗时判据都没有**。脚本会打 `耗时 NN … 秒`，那是给你自己看的；耗时随机器浮动，
  拿它当判据会让同一份代码时过时不过。所以参考解连跑多次结果完全一致。