双指针技术（Two Pointers）

【真题算法·第四期】

用两个指针在数组上一次遍历，替代双层循环的 O(n²) 暴力枚举——这是算法优化中最优雅的思维跃迁之一。

📖 一、知识点详解

1. 什么是双指针？

如果擂台法是关注一个变量的变化，那么双指针是关注两个变量的协同配合。

擂台法用一个指针（索引）遍历，用另一个变量记录当前最优值；而双指针用两个指针（索引）同时在数据结构上移动，相互配合

双指针（Two Pointers）是一种在数组或字符串中使用两个指针（索引）协同工作的算法技巧。两个指针按一定规则移动，在一次遍历中完成判断或计算。

擂台法： 一个指针遍历 + 一个变量记录最优

双指针（反向）： 一个指针从左向右 + 一个指针从右向左

双指针（同向）： 一个指针指向起点 + 一个指针向前探索

2. 三种经典模式

模式一相向双指针（左右夹逼）

两个指针从两端向中间移动，常见于判断回文、对称性等。

# 判断字符串是否对称（回文）

i, j = 0, len(s) - 1

while i < j:

    if s[i] != s[j]:

        return False

    i += 1

    j -= 1

return True

模式二同向快慢双指针

两个指针同向移动，一个快一个慢。常见于去重、滑动窗口预处理等。

# 去重：慢指针 i 指向已处理区域末尾，快指针 j 扫描

i = 0

for j in range(1, n):

    if a[j] != a[i]:

        i += 1

        a[i] = a[j]

return i + 1 # 去重后长度

模式三两端交替双指针

两个指针从两端交替选取，常见于擂台法同时求最大值和最小值。

i, j = 0, n - 1

while i <= j:

    if a[i] > a[j]:

        # 处理 a[i]（较大者）和 a[j]（较小者）

    else:

        # 处理 a[j]（较大者）和 a[i]（较小者）

    i += 1

    j -= 1

3. 双指针 vs 双层循环

核心区别：双指针不检查所有组合，而是利用「指针移动规则」跳过不可能的情况。

二、复杂算法的基石

双指针本身是一种基础技巧，许多更复杂的算法都建立在它的思想之上：

💡 规律：当一个算法需要两个索引协同移动时，本质上就是双指针思想的延伸。区别仅在于指针的移动规则和步长不同。

◆ ◆ ◆

🧪 二、真题举例

2016年01月选择题第11题：对称字符串

来源：[[201610-Q11-双指针]]

对称字符串的特征是从左到右读和从右到左读完全一样的。如 "abba" 是对称的，"abcba" 也是对称的。判断字符串是否对称的 Python 程序段如下：

s = input()

n = len(s)

k = 0

j = n - 1

for i in range(n // 2):

    # 加框处

if k == 0:

    print("对称")

else:

    print("不对称")

方框中的代码由以下三部分组成：

① j = j - 1

② if c1 != c2: k += 1

③ c1 = s[i]; c2 = s[j]

代码顺序正确的选项是（ ）

A.①③②   B.②③①   C.③②①   D.②①③

📝 解析

答案：C。先取第 i 个和第 j 个字符 → 比较是否不等 → j 向左移一位。顺序为 ③②①。

● ● ●

2024年01月选择题第11题：字符串处理

来源：[[202401-Q11-双指针-数组操作-字符串处理]]

若字符串 s 的值为 "abcde"，执行如下程序段后，变量 res 的值不可能是

from random import randint

s = "abcde"

res = ""

i, j = 0, len(s)-1

while i < len(s) and j >= i:

    if randint(0, 1) == 0:

        res += s[i]

        i += 1

    else:

        res += s[j]

        j -= 1

A. "abced"
B. "aecbd"
C. "aedbc"
D. "edcba"

📝 解析

本题考查随机数、逻辑判断、字符串及双指针。
根据代码可知，指针 i 和 j 分别指向字符串 s 的首尾两端。若随机数是 0，则从头部 i 位置取字符 s[i] 正向连接到 res 中；若随机数为 1，则从尾部 j 位置取字符 s[j] 正向连接到 res 中。由于指针 i、j 的步长都为 1，因此取字符时都是逐个变化的，不可能跳跃。
选项 A 正确：随机值分别为 00010 或 00011 即可得到。
选项 B 错误：当连接完 ae 后必然连接 b 或 d，不可能跳到 c。
选项 C 正确：随机值分别为 01100 或 01101 即可得到。
选项 D 正确：随机值分别为 11111 或 11110 即可得到。
答案：B。

● ● ●

2021年01月非选择题第15题：双人组队挑选算法

来源：[[202101-Q15-双指针]]

根据申请人的 QA 和 QB 值，从 m 个申请人中挑选 2 人组队参加某挑战赛。条件一是 2 人的 QA 值都必须大于指定参数 h；条件二是 2 人的 QA 值之差（较大值减较小值）小于 h。在满足上述两个条件的所有 2 人组合中，挑选 QB 值之和最大的一个组合。程序运行如下图所示：

（1）完善划线处代码。
（2）加框处代码有误，请修正。

idh = [6,1,11,2,4,20,7,13]

qa = [175,138,96,78,76,53,46,38] # QA值

qb = [15,26,41,38,30,27,31,29] # QB值

h = int(input("输入参数h："))

m = len(idh)

n = m

# 按QA降序排序，筛选QA>h

for i in range(m - 1):

    k = i

    for j in range(i + 1, m):

        if qa[j] > qa[k]:

            k = j

    if qa[i] > h: # (2)加框处：qa[i] > h

        if k != i:

            qa[i], qa[k] = qa[k], qa[i]

            qb[i], qb[k] = qb[k], qb[i]

            idh[i], idh[k] = idh[k], idh[i]

    else:

        ___①___

        break

max_sum = 0

s = "没有满足条件的组合"

# 查找符合条件的组合

for i in range(n - 1, 0, -1):

    j = i - 1

    while ___②___:

        if qb[i] + qb[j] > max_sum:

            s = f"组队结果：{idh[i]}号，{idh[j]}号"

            ___③___

        j -= 1

print(s)

📝 解析

（1）① i；② j >= 0 and abs(qa[i] - qa[j]) < h；③ max_sum = qb[i] + qb[j]
（2）原加框处 qa(i) > h 改正：qa[k] > h

◆ ◆ ◆

💡 三、解题要点

1先确定模式

拿到题先判断是相向、同向快慢还是两端交替，不同模式指针移动规则完全不同。

2指针初始位置

相向（i=0, j=n-1）、快慢（i=0, j=0或1）、交替（i=0, j=n-1）——初始值定错全盘皆错。

3移动条件

指针何时移动、每次移动多少，是决定算法正确性的关键。

4终止条件

i < j（相向）、j < n（快慢扫描完）、i <= j（交替）——少一个边界就多一次错误循环。

5避免越界

指针移出数组范围是最常见的 bug，始终检查 i >= 0 和 j < n。

双指针本质：用空间换时间的反面——不增加空间，而是利用数据结构的有序性或对称性，通过指针的智能移动来减少不必要的比较。

📌 总结

双指针是算法优化中最常用的技巧之一。掌握相向、同向快慢、两端交替三种模式，理解指针的初始位置、移动条件和终止条件，就能解决大多数双指针题目。更重要的是，许多高级算法（快排、归并、滑动窗口、Floyd 判圈等）本质上都是双指针思想的延伸。

如果这篇文章对你有帮助，欢迎 点赞、分享、推荐。