题目描述
思路解析动画文字版
记牢这一句:排序之后两端夹逼。两端和小于 target,就把左端配右边一整串一次数进来、左指针前进;两端和不小于 target,就让右指针后退。下面把数组排好序,一步步夹过去。
原始数组 · 先看未排序的样子：这是原始的 nums,顺序是乱的。双指针夹逼有个前提:数组必须有序,这样两端才分别是最小和最大,才能靠一次比较就判断出一整批。所以第一件事永远是排序。你先记住这 7 个数,下一帧它们就会排好队。
排序后 · 从小到大排好队：排好序后是 -7、-6、-2、-1、2、3、5,从左到右越来越大。现在最左边是最小的 -7,最右边是最大的 5。有了这个顺序,接下来两端一比就能判断一大片,而不用每两个数都单独相加去数。
安放双指针 · l 在最左,r 在最右：把左指针 l 放在下标 0,右指针 r 放在下标 6,底色框住的就是当前还要考察的窗口。计数器 ans 从 0 起步。核心的判断只看两端这两个数的和:小了就整批收,大了就缩右边。开始夹。
看两端之和 · nums[0] + nums[6]：当前窗口两端是 nums[0]=-7 和 nums[6]=5,它们的和是 -2。拿它和 target=-2 比:这个和不小于 target。既然最左的 nums[0] 配上最大的 nums[6] 都到不了严格小于,别的左端更大更不行,这个右端可以整个排除。
排除右端 · r 从 6 退到 5：两端和到不了严格小于,右端 nums[6]=5 是当前最大的数,它配上最小的左端都超标,配别的更超标,所以它不可能出现在任何合格的数对里,把它灰掉排除。右指针后退一格到 5,窗口缩小,继续看新的两端。
看两端之和 · nums[0] + nums[5]：当前窗口两端是 nums[0]=-7 和 nums[5]=3,它们的和是 -4。拿它和 target=-2 比:这个和严格小于 target。有序数组里 l 和它右边每个数搭配,和都不超过这个两端和,所以也全都小于 target。
整批计数 · 下标 0 配右侧 5 个：既然两端和都小于 target,那 nums[0] 和绿色这一串,从下标 1 一直到 5,每一个搭配都成立,一共 5 对,直接加进 ans,现在 ans 等于 5。下标 0 这个左端已经把它能配的都数完了,该让 l 前进一步了。
逐对验和 · 这 5 对都严格小于 target：不放心可以逐对核一下:nums[0]=-7 分别加上绿色这些数,得到的和是 -13、-9、-8、-5、-4,每一个都严格小于 -2。这正是排序的好处,一次比较就锁定一整批,不用一对一对去算。
看两端之和 · nums[1] + nums[5]：当前窗口两端是 nums[1]=-6 和 nums[5]=3,它们的和是 -3。拿它和 target=-2 比:这个和严格小于 target。有序数组里 l 和它右边每个数搭配,和都不超过这个两端和,所以也全都小于 target。
整批计数 · 下标 1 配右侧 4 个：既然两端和都小于 target,那 nums[1] 和绿色这一串,从下标 2 一直到 5,每一个搭配都成立,一共 4 对,直接加进 ans,现在 ans 等于 9。下标 1 这个左端已经把它能配的都数完了,该让 l 前进一步了。
逐对验和 · 这 4 对都严格小于 target：不放心可以逐对核一下:nums[1]=-6 分别加上绿色这些数,得到的和是 -8、-7、-4、-3,每一个都严格小于 -2。这正是排序的好处,一次比较就锁定一整批,不用一对一对去算。
看两端之和 · nums[2] + nums[5]：当前窗口两端是 nums[2]=-2 和 nums[5]=3,它们的和是 1。拿它和 target=-2 比:这个和不小于 target。既然最左的 nums[2] 配上最大的 nums[5] 都到不了严格小于,别的左端更大更不行,这个右端可以整个排除。
排除右端 · r 从 5 退到 4：两端和到不了严格小于,右端 nums[5]=3 是当前最大的数,它配上最小的左端都超标,配别的更超标,所以它不可能出现在任何合格的数对里,把它灰掉排除。右指针后退一格到 4,窗口缩小,继续看新的两端。
看两端之和 · nums[2] + nums[4]：当前窗口两端是 nums[2]=-2 和 nums[4]=2,它们的和是 0。拿它和 target=-2 比:这个和不小于 target。既然最左的 nums[2] 配上最大的 nums[4] 都到不了严格小于,别的左端更大更不行,这个右端可以整个排除。
排除右端 · r 从 4 退到 3：两端和到不了严格小于,右端 nums[4]=2 是当前最大的数,它配上最小的左端都超标,配别的更超标,所以它不可能出现在任何合格的数对里,把它灰掉排除。右指针后退一格到 3,窗口缩小,继续看新的两端。
看两端之和 · nums[2] + nums[3]：当前窗口两端是 nums[2]=-2 和 nums[3]=-1,它们的和是 -3。拿它和 target=-2 比:这个和严格小于 target。有序数组里 l 和它右边每个数搭配,和都不超过这个两端和,所以也全都小于 target。
整批计数 · 下标 2 配右侧 1 个：既然两端和都小于 target,那 nums[2] 和绿色这一串,从下标 3 一直到 3,每一个搭配都成立,一共 1 对,直接加进 ans,现在 ans 等于 10。下标 2 这个左端已经把它能配的都数完了,该让 l 前进一步了。
逐对验和 · 这 1 对都严格小于 target：不放心可以逐对核一下:nums[2]=-2 分别加上绿色这些数,得到的和是 -3,每一个都严格小于 -2。这正是排序的好处,一次比较就锁定一整批,不用一对一对去算。
两指针相遇 · 循环结束：现在 l 和 r 撞到一起了,窗口里凑不出两个不同的数,再没有新的数对可数,循环结束。整个过程里每一步要么整批计数、l 前进,要么排除右端、r 后退,两个指针一共只走了一趟,又快又不重不漏。
读出答案 · ans = 10：把三次整批计数加起来,5 对、4 对、再加 1 对,一共 10 对,这就是答案。回头看这套双指针:靠排序把数组理顺,再让两端夹逼,小了整批收、大了缩右边,时间只花在排序和这一趟扫描上,比两两枚举快得多。
边界想清:和等于 target 不算、和严格小于才计、负数按数值大小一视同仁地比较。
面试重点:排序造出单调性、两端和整批判定、瓶颈在排序 O(n log n)、也可换成排序加二分。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def countPairs(self, nums: List[int], target: int) -> int: nums.sort() ans = 0 for j, x in enumerate(nums): i = bisect_left(nums, target - x, hi=j) ans += i return ans复杂度
- 时间：O(n log n)，排序占 O(n log n),是主要开销。之后双指针从两端往里夹,l 只增、r 只减,两个指针合起来最多走 n 步,这一趟是 O(n)。若用排序加二分的写法,后半段是 n 次二分共 O(n log n),两种写法总量都由排序主导,同为 O(n log n)
- 空间：O(1) 到 O(n)，按峰值算。除了几个指针和计数器,双指针本身只用 O(1) 辅助空间;排序的内部开销分语言不同,不计排序则 O(1),要计则 C 加加 和 Java 递归栈约 O(log n)、Python 的 Timsort 最坏 O(n)
易错点
面试追问把动画讲成自己的话
追问这题为什么排序后能用双指针?
追问除了双指针还能怎么做?
追问复杂度是多少,瓶颈在哪?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
搜索旋转排序数组
LeetCode 33 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题