双指针：两个下标的配合

第 9 课的两种走法处理的是「连续一段」的问题：前缀和把区间和变成两次减法，滑动窗口用一个窗口框住一段并让它只往右滑。那一课里两个下标 l 与 r 记的是同一段区间，走向也相同。

这一课要解的题换了一类：有序数组里找一对和为目标值的数、原地去掉重复元素、判断一个序列是不是回文、把两个有序数组合并成一个。这些题的共同点是：一个下标不够用，常见的做法是再套一层循环。第二个下标用对了，循环就从平方降到线性——同样是两数之和，n = 16000 时两层循环要跑 3.3 秒，对撞指针 0.0017 秒（文末的实测表）。

配合的方式有两种，两个名字在算法竞赛里已经固定下来了。对撞指针的两个下标分别从两端出发、相向而行，用来处理配对与判定；快慢指针的两个下标同向而行、但职责不同，一个负责读、一个负责写，用来原地整理一段数据。它们与第 9 课的滑动窗口落在同一族写法里（统称双指针），区别在于两个下标各自的走向与职责：滑动窗口的两个下标是同一段区间的两条边，本课的对撞指针是两条相向收拢的边界，快慢指针是一条读位置加一条写位置。

四个任务按下面的顺序展开：先讲对撞指针（两数之和、回文判定），再讲快慢指针（原地去重），最后讲两个指针各管一个数组的合并。每一段都配一段能直接跑的代码，并用本机实测的输出说明两个指针各自保证了什么。

对撞指针：左右相向

设数组 a 已经按非降序排好，要找一对下标 i < j 使 a[i] + a[j] = S。最直接的写法是枚举所有下标对，代价 O(n^2)。对撞指针给出的是另一种走法：取 l = 0、r = n - 1，每轮比较 a[l] + a[r] 与 S，按比较结果移动其中一个下标。

这个走法的名字来自两个下标的走向：l 只往右走，r 只往左走，两者每轮靠近一格，最后相遇。三条移动规则如下。

第二条与第三条都要靠有序这条前提才成立，第三节会专门说它。先说清两个指针各自保证什么。每一轮比较开始之前，下面这条命题都成立：

若答案存在，则答案的两个下标都落在闭区间 [l, r] 之内。 这条命题就是这份写法的循环不变式：初始时 l = 0、r = n - 1，区间覆盖整个数组，命题当然成立；每轮丢掉 a[l] 或 a[r] 时，被丢的那一格由上面两条规则保证不可能出现在答案里，于是区间缩小之后命题依然成立；l 与 r 相遇（l \ge r）时区间里剩下的候选不足两个下标，答案不存在。

两个指针各自的保证也就能分开写了：

• l 保证：区间 [0, l) 里的每个元素都不可能出现在答案里。这些元素要么已经作为左端与当时的 a[r] 配过、和偏小，要么由不变式排除在候选区间之外。
• r 保证：区间 (r, n - 1] 里的每个元素都不可能出现在答案里，理由对称。

def two_sum_sorted(a, target):
    """有序数组里找一对和为目标值的数，返回下标对；无解返回 None。"""
    l = 0
    r = len(a) - 1
    while l < r:
        s = a[l] + a[r]
        if s == target:
            return (l, r)
        if s < target:
            l += 1
        else:
            r -= 1
    return None


a = [1, 4, 5, 9, 11, 15]
print(two_sum_sorted(a, 10))        # (0, 3)：1 + 9
print(two_sum_sorted(a, 20))        # (2, 5)：5 + 15
print(two_sum_sorted(a, 100))       # None：没有这样的两数

(0, 3)
(2, 5)
None

第一组数据里，1 + 15 = 16 偏大，r 往左收；1 + 11 = 12 还是偏大，r 再收；1 + 9 = 10 命中。第二组里 1 + 15 偏小，l 往右走，走到 5 + 15 = 20 命中。前两组各走 3 轮就命中。第三组没有答案，两个指针走 5 轮后相遇（l = r = 5）而结束，正好是 n - 1 轮。

代价是两条：每轮至少有一个指针移动一格，指针合计最多走 n - 1 格，所以时间 O(n)；全程只用两个整数下标和几次加法，额外空间 O(1)。第 3 课那张价格表里，按下标取元素是 O(1)，对撞指针每次比较正好只做两次取值与一次加法。

该收一格还是收到位

上面的 while l < r 版本里，每轮只动一格，写成 if 与写成 while 都对——外层循环一定会带着新的 (l, r) 回来再比一次，没收够的格数还有机会在下一轮补上。把外层换成 for l in range(len(a)) 之后，这两种写法就分开了：l 一去不回，同一个 l 与更小的 r 的组合再没有人检查。

看下面的对照。数组 a = [1, 4, 5, 9, 11]，目标值 10，答案只有一对：1 + 9 = 10，下标 (0, 3)。

def two_sum_if(a, target):
    """右指针每轮只收一格。"""
    r = len(a) - 1
    for l in range(len(a)):
        if l >= r:
            break
        s = a[l] + a[r]
        if s == target:
            return (l, r)
        if s > target:
            r -= 1
    return None


def two_sum_while(a, target):
    """右指针一直收到不再偏大。"""
    r = len(a) - 1
    for l in range(len(a)):
        while l < r and a[l] + a[r] > target:
            r -= 1
        if l >= r:
            break
        if a[l] + a[r] == target:
            return (l, r)
    return None


a = [1, 4, 5, 9, 11]
print(two_sum_if(a, 10))        # None：漏了 1 + 9
print(two_sum_while(a, 10))     # (0, 3)：1 + 9

None
(0, 3)

两个函数只差一个关键字，一个返回 None，一个返回正确答案。把 if 版的每一轮状态打出来，漏在哪一步就清楚了：

第 1 轮结束时 r 已经收到 3，(0, 3) 这一对本来就该在第 2 轮被检查。if 版在这一轮之前就把 l 交给了 for，l 变成 1，于是 (0, 3) 再也没有出现过。判据可以写成一句话：移动一格之后，我还会回到同一个 (l, r) 组合重新比一次吗？ 外层是 while l < r 会，if 够用；外层是 for l 不会，该用 while 的地方写成 if 就漏解。

还有一处细节：while 版的条件里带了 l < r。它保证区间里始终至少剩下两个候选下标；r 收到与 l 相遇时立刻停手，不让两个下标交错——交错之后再比较，得到的一对下标次序也就反了。

有序这条前提

上面两条移动规则都建立在「数组已按非降序排好」之上：a[l] + a[r] 偏小时，要有 a[l] + a[j] \le a[l] + a[r] 对一切 j \le r 成立，才能断定 a[l] 与 [l, r] 内任何元素的和都小于 S。这条不等式只在有序时成立。数组无序时，丢掉的那一格完全可能是答案的一半。

取 a = [2, 7, 4, 1]、S = 9，答案 2 + 7 = 9 在下标 (0, 1)。

def two_sum_brute(a, target):
    """两层循环：枚举所有下标对。"""
    n = len(a)
    for i in range(n):
        for j in range(i + 1, n):
            if a[i] + a[j] == target:
                return (i, j)
    return None


a = [2, 7, 4, 1]
print(two_sum_brute(a, 9))      # (0, 1)：2 + 7
print(two_sum_sorted(a, 9))     # None：2 与 7 都被丢掉了
print(sorted(a))                # [1, 2, 4, 7]
print(two_sum_sorted(sorted(a), 9))   # (1, 3)：2 + 7，下标是排好序之后的

(0, 1)
None
[1, 2, 4, 7]
(1, 3)

对撞版在这组数据上走的每一步，都在丢掉答案需要的元素：

l = 0  r = 3  a[l] + a[r] = 3  偏小，丢掉 a[0] = 2
l = 1  r = 3  a[l] + a[r] = 8  偏小，丢掉 a[1] = 7
l = 2  r = 3  a[l] + a[r] = 5  偏小，丢掉 a[2] = 4
l 与 r 相遇，没有找到

第 1 步看到 2 + 1 = 3 偏小，就把 2 丢了；可是 2 要配的元素是 7，它排在更远的位置，r 当时指着的 1 比 7 小，于是「和偏小」这个信号在这一步给出的结论是错的。7 在第 2 步被丢，原因相同。把数组排好再对撞，两步之内就命中：1 + 7 = 8 偏小、2 + 7 = 9 命中。

能用的判断办法有两条：

• 题目给的数组已经有序，或者允许先排序：sorted(a) 之后再用对撞指针，此时得到的是排好序之后的下标。
• 题目要的是原来那对下标：排序会打乱下标，这条路走不通，这类题要换别的写法。

快慢指针：一读一写

第二个任务是原地去重：数组已排好序，把重复的值去掉，只留每个值一次，并且不使用额外空间。「不使用额外空间」是题目明写的条件，也是这一课的一个考点：原地改写把额外空间压到 O(1)，付出的是写错之后不容易发现。

先看现成的删除操作能做什么。官方教程里的口径是：list.remove(value) 从列表中移除第一个值为 value 的条目，没有这个值就抛 ValueError；按下标删除用 del a[i]，del a[2:4] 删掉一段切片，del a[:] 清空整个列表。这些操作都只改原列表、返回 None，而且都要把后面的元素整体往前搬一格——第 3 课的价格表里，lst.pop(i) 与 lst.insert(i, x) 都是 O(n)，越靠前越贵。删 k 个重复值就是 O(kn)，n = 10^5 时这条路走不通。

快慢指针把「找到重复」与「搬动元素」合成一趟扫描，两个下标的职责分得很清楚：

• fast 是读位置：它从 1 开始，每轮往右走一格，保证 a[fast] 左边的每个位置都已经被看过一次。
• slow 是写位置：它指向已经整理好的那一段的最后一个元素，保证 [0, slow] 里的值互不相同、且相对顺序与原来一致。

每一轮开始之前，下面两条同时成立：

• [0, slow] 是整理好的部分：前缀里的值两两不同、按原来的顺序排列；
• (slow, fast) 之间的位置已经处理过，里面的内容不再需要；[fast, n) 还没有看过。

判断规则只有一条：a[fast] 与 a[slow] 相同时，这个值是重复的，丢掉；不同时，它是第一个出现的值，必须留下来——先把 slow 往前挪一格，再把 a[fast] 写到新的 a[slow] 上。这两步的先后顺序不能换：先写再挪，会把已整理部分的最后一个值覆盖掉。

def dedup_sorted(a):
    """有序数组原地去重，返回值是去重后剩下的元素个数。"""
    if len(a) == 0:
        return 0
    slow = 0
    for fast in range(1, len(a)):
        if a[fast] != a[slow]:
            slow += 1
            a[slow] = a[fast]
    return slow + 1


b = [1, 1, 2, 3, 3, 3, 5]
k = dedup_sorted(b)
print(k, b[:k])                     # 4 [1, 2, 3, 5]
print(b)                            # 只有前 k 项是答案

4 [1, 2, 3, 5]
[1, 2, 3, 5, 3, 3, 5]

第二行输出要读准：函数返回的是个数 k，只保证 b[:k] 是去重后的结果，b[k:] 里是上一轮留下来的旧值，不用清也不用管。这与返回一个新列表的函数不同，原地改写的函数必须把「哪一段有效」交代出去，k 就是这份交代。

代价是 O(n) 时间与 O(1) 额外空间：fast 走 n - 1 格，slow 最多走 n - 1 格，两个下标合计 O(n)，且没有造新列表。收尾打印用的 b[:k] 是一次切片，第 3 课讲过它会复制出 k 个元素、代价 O(k)；这里用一次没关系，它的位置在循环之外。

写入位置忘了往前挪

读位置与写位置混在一起，是原地改写最容易出错的地方。把上面那段代码里的 slow += 1 删掉，slow 会一直停在 0，所有的值都往 a[0] 上写：

def dedup_forget_write(a):
    """忘记了把写入位置往前挪：所有不同的值都写到 a[0]。"""
    if len(a) == 0:
        return 0
    slow = 0
    for fast in range(1, len(a)):
        if a[fast] != a[slow]:
            a[slow] = a[fast]
    return slow + 1


b = [1, 1, 2, 3, 3, 5]
print(dedup_forget_write(b))    # 1：声称只剩 1 个元素
print(b)                        # 原数组被写花

1
[5, 1, 2, 3, 3, 5]

这个错版的返回值和数组内容都是错的，两个错还能互相解释。逐轮打出来看：

第 3 轮把 3 写进了 a[0]，第 4 轮再读 a[slow] 时读到的就是刚写下去的那个 3，于是「与已整理部分的最后一个值相同」这个判断被自己的写入结果带偏，那个位置上原本要留下来的 3 被当成了重复值丢掉。错版最终声称去重后只剩 1 个元素，而原数组前几项已经被写花成 [5, 1, 2, 3, 3, 5]；正确版的答案是 4 与 [1, 2, 3, 5]。

防它的办法是先分清两个位置：fast 那一格是读的，slow 那一格是写的；slow += 1 与 a[slow] = a[fast] 是配成一对的动作，中间不插别的语句。上面的不变式也正好用在这里：只要 [0, slow] 是整理好的部分，写入位置就永远落在它的下一格，读到的旧值不会是自己写下去的。

回文判定：两头向中间

对撞指针还管一类题：判定。判断一个序列是不是回文，意思是它与自己的逆序逐项相等。列表与字符串都按下标取元素、都用 len 取长度（官方教程把它们放在「序列」这一节里讲），所以同一段代码对两者都成立。

两个下标的职责在这里完全对称：l 从左往右、r 从右往左，每轮比较 s[l] 与 s[r]。每一轮开始之前的命题是：

• [0, l) 与 (r, n - 1] 已经逐对比较过，每一对都相等；
• 因此整个序列是不是回文，只剩 [l, r] 这一段还没查。

l 保证：左边已经比过的部分不需要再比。r 保证：右边已经比过的部分不需要再比。移动条件是两条，与两数之和那种「只动一个」不同——比较结果只有相等与不相等两种，不相等直接给出结论，相等则两个指针一起动。

def is_palindrome(s):
    """判断序列 s 是不是回文。"""
    l = 0
    r = len(s) - 1
    while l < r:
        if s[l] != s[r]:
            return False
        l += 1
        r -= 1
    return True


print(is_palindrome('上海自来水来自海上'))   # True
print(is_palindrome('abccba'))               # True
print(is_palindrome('abcabc'))               # False
print(is_palindrome([1, 2, 3, 2, 1]))        # True

True
True
False
True

第三条数据 abcabc 在第 1 轮就退出：s[0] 是 a、s[5] 是 c，两者不相等，不必再比。第四条数据是奇数长度，两个指针在中间那一格相遇（l = r = 2），循环条件 l < r 不成立而正常结束——奇数长度的中间那一项与自身相等，不需要单独处理。时间 O(n)，额外空间 O(1)。

合并两个有序数组

最后一个任务是把两个已经排好序的数组拼成一个有序数组，这是归并排序里的一步。两个下标各管一个数组，都从各自的头部出发：

• p 指向 a 中还没被取走的最小元素，即 a[p] 是 a 剩下的部分的最小值；
• q 指向 b 中还没被取走的最小元素；
• 已经放进结果列表的那一段，是「两个数组已取走的元素」合并后的有序前缀，且其中每一项都不大于 a[p] 与 b[q]。

移动条件是「谁小谁走」：比较 a[p] 与 b[q]，小的那个被取走、它所属的下标加一。相等时取 a 的那一个（<=），这样结果里同值的相对次序与输入的先后一致。

def merge_sorted(a, b):
    """把两个有序列表合并成一个有序列表。"""
    p = 0
    q = 0
    out = []
    while p < len(a) and q < len(b):
        if a[p] <= b[q]:
            out.append(a[p])
            p += 1
        else:
            out.append(b[q])
            q += 1
    while p < len(a):
        out.append(a[p])
        p += 1
    while q < len(b):
        out.append(b[q])
        q += 1
    return out


print(merge_sorted([1, 3, 5, 7], [2, 4, 6]))   # [1, 2, 3, 4, 5, 6, 7]
print(merge_sorted([1, 2, 3], [2, 2, 9]))      # [1, 2, 2, 2, 3, 9]

[1, 2, 3, 4, 5, 6, 7]
[1, 2, 2, 2, 3, 9]

主循环走到某一个数组取空为止，剩下的那一个数组整体都比已取走的大，所以后面两个 while 把它整段接上即可，不必逐个比较。时间 O(n + m)：两个下标合计走 n + m 格。空间 O(n + m)：结果放在新列表里。

同一件事有现成的写法：sorted(a + b)。a + b 先造一个 n + m 项的新列表，再交给 sorted。两条路都跑一遍，结果一样、耗时不一样（n = m = 10^5，本机实测、非通用值）：

手写双指针合并 0.0342 秒
sorted(a + b)  0.0067 秒
两个结果一样 True 长度 200000

sorted 快了约 5 倍——它是内置函数，循环跑在 C 层；两段各自有序时，它用的排序正好能把两段直接接起来。这个差距不影响选择：题目要求 O(1) 额外空间时 sorted(a + b) 用不了（它必然造一个新列表），需要在合并途中顺手做别的判断时也用不了（比如只取前 k 项、或者比较的不是元素本身）。这类场合就得自己写双指针；写熟它的收益是把「两个下标各保证什么」练成本能，速度并不是它的长处。

要求原地合并、并且第一个数组末尾已经留好空位时，还有一个从后往前写的版本：p、q 分别指向两个数组没被取走的最大元素，写入位置 w 从 m + n - 1 往前移，每次把较大的那个写到 a[w]。从后往前写的好处是每个位置只被写一次、不会覆盖还没读到的元素；往中间 insert 一次就要 O(n)（第 3 课的价格表），从后往前写每次都是 O(1)。

def merge_into(a, m, b):
    """a 的前 m 项已排好、后面留了 len(b) 个空位，把 b 原地合并进 a。"""
    p = m - 1
    q = len(b) - 1
    w = m + len(b) - 1
    while q >= 0:
        if p >= 0 and a[p] > b[q]:
            a[w] = a[p]
            p -= 1
        else:
            a[w] = b[q]
            q -= 1
        w -= 1
    return a


c = [1, 4, 7, 0, 0, 0]
print(merge_into(c, 3, [2, 5, 6]))   # [1, 2, 4, 5, 6, 7]

[1, 2, 4, 5, 6, 7]

两数之和的两种写法实测

同一道两数之和，两层循环与对撞指针在四档规模上的耗时（n 个互不相同的随机整数，答案落在数组中间；本机实测、非通用值）：

两列数字要分开读：

• 两层循环那一列：n 翻一倍，耗时从 0.770 秒涨到 3.347 秒，是 4.3 倍，正是 O(n^2) 的形状。第 2 课那把尺子在这里给出的是：1 秒时限下这一版只能扛到 n \approx 9000。
• 对撞指针那一列：绝对值都在毫秒以下，刻度太小，这三档之间的秒数有测量波动；它是不是线性的，看最后一列更可靠——指针每一轮只走一格，n = 16000 时合计 15999 轮，正好是 n - 1，每一轮又只做常数次操作。这组数据是它的最坏情形，总代价依然是线性的。
• 在 n = 16000 这一行，两者相差约 1960 倍。这个差距来自走法的改变，与代码写得紧不紧凑无关：两版都是普通写法。

这一课用到的写法

有序数据上的配对与去重是省赛里的低难度高频题，这四道题用到的两种配合方式覆盖了这一类题的主要写法，写熟能省下大量调试时间。蓝桥杯的题面常把「有序」「原地」「不使用额外空间」写在数据范围与说明里，读题时把这三处标出来，用哪套写法基本就定了。

配套项目「AI 刷题助手」在这一步要能说出两件事：这题的两个指针各是什么，以及各自保证什么。这两句是判断一条建议能不能照着写的最小信息——只报出「用双指针」而说不出两个下标的移动条件，这条建议就没法照着写。

• Python 官方文档 · 数据结构列表的 remove、del、切片与序列的公共操作，本课原地删除与原地改写的官方说法出自这里
• OI Wiki · 复杂度时间复杂度与空间复杂度的口径，本课「翻倍涨四倍、翻倍涨两倍」的读法照它
• OI Wiki · 前缀和与差分第 9 课同一条来源；本课与它对齐「区间」「前缀和」的说法，本课的题不走这条路
• 《算法竞赛进阶指南》双指针与尺取法（具体章节待核实）本地教材：双指针与尺取法的推导，可作参考书查
• 洛谷题单：双指针（模板题起步）题单，在洛谷站内检索「双指针」题单