2024年9月21号那场练习赛里我被一道叫“奇怪球”的题卡了二十多分钟。题面叙述挺玄乎什么魔法球、魔力值、能量阈值剥掉包装之后其实就是一道非常典型的双指针计数题。这篇文章我把整个思考和实现过程完整写下来希望给正在刷双指针、或者准备算法面试的朋友一点参考题目怎么抽象、双指针为什么能优化、Python怎么落地以及那些特别容易踩的细节坑。好下面直接进正文。1. 题目长什么样从玄学故事到数学建模1.1 原题的故事包装这道题的原题描述大概是这样的具体措辞我记不全但核心意思不变实验室里有 n 个奇怪的球排成一排每个球上写着一个整数叫做“魔力值”。神奇的是魔力值可以是负数也可以非常大这正是“奇怪”的来源。现在给你一个阈值 k问有多少对不同的球它们魔力值之差的绝对值不超过 k数据范围我记得很清楚n 最大到 2×10^5魔力值的绝对值最大到 10^9k 同样可以到 10^9。这个范围基本就是在明示别想用 O(n²) 的暴力老老实实优化到 O(n log n) 或者 O(n)。1.2 抽象成数学模型剥掉故事之后这个问题的本质非常简单给定长度为 n 的整数数组 a统计满足 i j 且 |a[i] - a[j]| k 的无序对数量。这里的“无序对”意思是只算一次比如 (i, j) 和 (j, i) 是同一对。题面里如果没特别说明顺序通常都是按无序对处理读题的时候这个细节要注意不然最后答案会差一倍。1.3 为什么暴力解法过不了第一时间能想到的肯定是双重循环把所有对都检查一遍for i in range(n): for j in range(i1, n): if abs(a[i] - a[j]) k: ans 1这个写法思路没错但 n2×10^5 的时候内层循环大约要执行 2×10^10 次也就是 200 亿次比较。就算 Python 每秒能跑 5000 万次简单操作也得几百秒才能结束评测系统限时通常只有 1~2 秒暴力必挂。注意看到“n 到 10^5 甚至 10^6 级别”的计数类题目第一反应就该是双指针、二分、前缀和或者哈希这类 O(n log n)/O(n) 级别的优化手段。2. 双指针思路的核心排序消除绝对值2.1 关键观察排序后绝对值会“自动消失”条件里有绝对值处理起来比较麻烦。一个非常经典的处理方式就是先排序。排序之后数组单调不减如果 i j那么 a[j] a[i]于是|a[i] - a[j]| a[j] - a[i]原始条件 |a[i] - a[j]| k 就等价于a[j] - a[i] k绝对值符号没了问题变成对于每个位置靠前的元素数一数它后面有多少个元素与它的差值不超过 k。排序不会改变“有多少对满足条件”这个答案因为差值的大小关系在排序后保持不变只是我们把所有元素按大小重新排列了一遍而已。2.2 单调性双指针能跑的底层原因假设数组已经排好序现在定义两个指针left当前考察的元素下标right满足 a[right] - a[left] k 的最远下标当 left 向右移动一位变成 left1 时因为 a[left1] a[left]同样一个 right 位置如果之前满足 a[right] - a[left] k那么现在必然也满足a[right] - a[left1] a[right] - a[left] k也就是说left 向右走的时候right 是不可能向左回退的它只会继续向右扩展。这种“两个指针都朝同一个方向走谁也不回头”的性质就是双指针能保证线性时间复杂度的根本原因。2.3 计数逻辑每个 left 贡献多少对对于当前的 left我们找到最大的 right 满足 a[right] - a[left] k那么在 left 右侧从 left1 到 right 这 (right - left) 个位置每一个都能和 left 组成一个合法对。累加进答案即可。注意这里不要写成 right - left 1因为 left 自己不能和自己配对。统计完当前 left 之后left 继续右移right 保持在原地或继续右移不需要重新扫描整体就是 O(n) 的。2.4 复杂度分析整个算法分两步排序O(n log n)双指针扫描O(n)因为 left 和 right 最多各移动 n 次合起来是 O(n log n)空间复杂度 O(1)如果不考虑排序内部使用的栈空间。这个复杂度在 n2×10^5 的规模下完全没问题Python 大概几十毫秒就能跑完。3. Python 实现与逐行讲解3.1 标准写法先给出最标准的双指针实现def count_pairs(a, k): a.sort() n len(a) ans 0 right 0 for left in range(n): if right left: right left while right 1 n and a[right 1] - a[left] k: right 1 ans right - left return ans这段代码非常短但里面有三处细节值得掰开揉碎讲清楚。3.2 三个关键细节第一个细节是if right left: right left。正常情况下 right 不会小于 left因为同一个元素不能和自己配对right 至少应该等于 left。但为了绝对安全在循环开头做一次修正防止某些边界情况比如上一轮 right 停在原地而 left 已经越过了它导致 while 条件里出现索引越界或者漏算。第二个细节是 while 循环里的right 1 n。这个条件和a[right 1] - a[left] k一起控制右指针扩展。注意判断的是“下一个位置能不能扩展”而不是先移动再判断这样能避免 right 越界之后还要回退的麻烦。第三个细节是ans right - left。每次累加的是当前 left 右侧所有能与 left 配对的位置数量。right 指向的是“合法的最后一个位置”所以数量是 right - left 而不是 right - left 1。3.3 用测试用例验证我写题的习惯是先在心里跑几个小例子再提交这里给大家留几个常用的验证用例输入k输出说明[]50空数组[5]1000单元素没有对[1,1,1,1]064个相同值C(4,2)6[3,1,4,1,5]13(1,1),(3,4),(4,5)[-1,2,3]21负数也正常处理逐个验证一下第三个例子[3,1,4,1,5]k1。排序后是 [1,1,3,4,5]。left0值1right 先走到 1a[1]-a[0]01再试 a[2]-a[0]21停。ans 1-01。left1值1right 不动a[2]-a[1]21停。ans 1-10。left2值3right 已经是1修正为2。a[3]-a[2]11right3a[4]-a[2]21停。ans 3-21。left3值4a[4]-a[3]11right4。ans 4-31。left4值5right4a[5] 越界ans 0。最后 ans 10110 3。每个合法对都不重不漏。3.4 另一种等价写法二分查找双指针之外每个元素配合二分也能做。对排序后的数组对于每个 i用二分找到“最后一个值 a[i]k”的位置 idx那么 i 后面能配对的元素就是 idx - i 个。Python 可以直接用 bisect_rightfrom bisect import bisect_right def count_pairs_bisect(a, k): a.sort() ans 0 for i, x in enumerate(a): idx bisect_right(a, x k) - 1 ans idx - i return ans这个写法同样正确复杂度也是 O(n log n)。但双指针除了少一个 log更重要的是它培养的“单调性思维”能直接迁移到很多滑窗类问题上所以我更推荐大家把双指针版本吃透。4. 双指针的变体奇怪球还能怎么玩双指针不是一个死板的模板根据指针移动方向可以分成好几种形态。这里借着“奇怪球”的设定讲两个最常考的变体。4.1 变形一两数之和小于等于 k如果题目改成“统计两数之和 k 的对数”排序之后双指针的移动方向就变了不再是同向而是从两端往中间走。思路很简单left 指向最小值right 指向最大值。如果 a[left] a[right] k说明 a[left] 和 left 右侧任意一个数相加都不超过 k直接累加 right - left 对然后 left 右移否则说明 a[right] 太大了right 左移。def count_sum_pairs(a, k): a.sort() left, right 0, len(a) - 1 ans 0 while left right: if a[left] a[right] k: ans right - left left 1 else: right - 1 return ans这个“相向双指针”是两数之和问题最经典的解法。同样利用了单调性——数组有序之后固定 left移动 right 的过程就是不断缩小可行范围的过程。4.2 变形二三色球原地排序荷兰国旗问题“奇怪球”如果从魔力值换成颜色比如红白蓝三种颜色要求把数组原地排成“红、白、蓝”三段那就变成了荷兰国旗问题。这个用三个指针 low、mid、high 解决本质上是双指针思想的再扩展。def sort_colors(nums): low, mid, high 0, 0, len(nums) - 1 while mid high: if nums[mid] 0: # 红色换到前面 nums[low], nums[mid] nums[mid], nums[low] low 1 mid 1 elif nums[mid] 1: # 白色已经在中间直接跳过 mid 1 else: # 蓝色换到后面 nums[mid], nums[high] nums[high], nums[mid] high - 1这里有个特别容易误解的地方为什么 nums[mid] 0 时交换后 mid 要加 1而 nums[mid] 2 时交换后 mid 不加 1原因很简单。把 0 换过来时从 low 位置换过来的元素是已经被检查过的low 一直走在 mid 前面它不可能是 2所以 mid 可以放心前进。但把 2 换过来时从 high 位置换过来的元素是从来没被检查过的它可能是 0也可能是 1所以 mid 必须停在原地再判断一次。4.3 双指针家族对比把常见的双指针形态放一起对比以后看到题目能更快定位用哪种形态典型场景指针移动方式复杂度同向双指针计数配对、滑窗、最长无重复子串left/right 都只向右O(n)相向双指针两数之和、回文判断、容器盛水left 右移 / right 左移O(n)快慢指针链表判环、找中点、数组去重速度不同O(n)三指针分区荷兰国旗、三色排序low/mid/high 配合O(n)5. 常见问题与排查技巧写双指针最怕的不是思路不会而是代码看起来对了、跑起来就是不对。我把这些年踩过的坑集中整理一下。5.1 经典错误right 每次从 left 重新开始这是我见过最普遍的低级错误。有人写for left in range(n): right left while right 1 n and a[right 1] - a[left] k: right 1 ans right - left单独看这个循环内部逻辑没问题但它每次把 right 重置回 left导致整体复杂度退化成 O(n²)。当 k 很大时比如 k 取 10^9每个 left 都会把 right 扫到数组末尾n2×10^5 时就是 4×10^10 次操作和暴力没区别评测必超时。牢记双指针的精髓是 right 不回退。left 移动之后right 应该在上一次基础上继续扩展而不是重新开始。5.2 忘记排序就直接上双指针双指针能够工作的前提是数组有序。如果不排序left 和 right 之间根本不存在单调关系right 是否该回退完全不可控答案肯定是错的。我建议在动手写代码之前先在注释里写清楚“我准备对数组做什么操作”如果是双指针计数排序这一行必须排在所有指针操作之前没有例外。5.3 重复元素导致重复计数或漏计数数组里有大量重复值时双指针的计数依然正确前提是你要确保每个 pair 只被统计一次。在“a[j] - a[i] k”这个版本里我们是固定 left 为较小下标所有配对都是 left 右侧的元素所以不会重复。但如果把计数逻辑改成“对每个值统计出现次数然后组合数”也 OK只是要注意 C(cnt, 2) 的计算方式别在 cnt 为 1 时也算出 0 之外的数。5.4 输入规模大的时候记得优化输入输出n 到 2×10^5 时直接用 sys.stdin.read() 一次性读入再 split比逐行 input() 快得多import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) n, k data[0], data[1] a data[2:2n] print(count_pairs(a, k)) if __name__ __main__: main()这个细节在本地可能感觉不明显但在线评测数据量大时能省下不少运行时间。Python 刷题一定要养成用 buffer 读输入的习惯。5.5 万能调试法对拍最后分享一个我刷题时最常用的调试技巧——对拍。写一个 O(n²) 的暴力函数再写一个双指针的快速函数随机生成大量小数组比较两者结果import random def brute(a, k): ans 0 for i in range(len(a)): for j in range(i1, len(a)): if abs(a[i] - a[j]) k: ans 1 return ans for _ in range(10000): a [random.randint(-10, 10) for _ in range(random.randint(0, 20))] k random.randint(0, 15) if count_pairs(a[:], k) ! brute(a, k): print(出错:, a, k) break else: print(全部通过)只要对拍能跑过几千组随机数据你的实现基本就可以放心提交了。很多隐蔽的边界问题比如越界、重复计数、排序影响都逃不过这招。刷双指针这类题我个人最大的体会是别急着写代码先问自己三个问题。第一排序会不会改变答案第二left 向右走的时候right 会不会需要回退第三每个计数分支会不会重复或者遗漏把这三个问题想清楚双指针题目至少能答对八成。这道“奇怪球”虽然包装花哨但扒开之后就是排序加同向双指针希望这篇记录能让你少走一点我走过的弯路。
