统计和小于目标的下标对数目 图解题解
这道题到底在问什么
- 输入
- nums=[-1,1,2,3,1], target=2
- 输出
- 3
- 输入
- nums=[-6,2,5,-2,-7,-1,3], target=-2
- 输出
- 10
先想最直接的笨办法
把三次整批计数加起来,5 对、4 对、再加 1 对,一共 10 对,这就是答案。回头看这套双指针:靠排序把数组理顺,再让两端夹逼,小了整批收、大了缩右边,时间只花在排序和这一趟扫描上,比两两枚举快得多。（动画第 23 步）
最优解：一步一步想明白
- 3记牢这一句:排序之后两端夹逼。两端和小于 target,就把左端配右边一整串一次数进来、左指针前进;两端和不小于 target,就让右指针后退。下面把数组排好序,一步步夹过去。
- 4第一步:排序这是原始的 nums,顺序是乱的。双指针夹逼有个前提:数组必须有序,这样两端才分别是最小和最大,才能靠一次比较就判断出一整批。所以第一件事永远是排序。你先记住这 7 个数,下一帧它们就会排好队。
- 5有序:可以夹逼了排好序后是 -7、-6、-2、-1、2、3、5,从左到右越来越大。现在最左边是最小的 -7,最右边是最大的 5。有了这个顺序,接下来两端一比就能判断一大片,而不用每两个数都单独相加去数。
- 6窗口 [0, 6]把左指针 l 放在下标 0,右指针 r 放在下标 6,底色框住的就是当前还要考察的窗口。计数器 ans 从 0 起步。核心的判断只看两端这两个数的和:小了就整批收,大了就缩右边。开始夹。
- 7和偏大:缩右边当前窗口两端是 nums[0]=-7 和 nums[6]=5,它们的和是 -2。拿它和 target=-2 比:这个和不小于 target。既然最左的 nums[0] 配上最大的 nums[6] 都到不了严格小于,别的左端更大更不行,这个右端可以整个排除。
- 8排除,r 左移两端和到不了严格小于,右端 nums[6]=5 是当前最大的数,它配上最小的左端都超标,配别的更超标,所以它不可能出现在任何合格的数对里,把它灰掉排除。右指针后退一格到 5,窗口缩小,继续看新的两端。
- 9和偏小:可整批数当前窗口两端是 nums[0]=-7 和 nums[5]=3,它们的和是 -4。拿它和 target=-2 比:这个和严格小于 target。有序数组里 l 和它右边每个数搭配,和都不超过这个两端和,所以也全都小于 target。
- 10ans = 5既然两端和都小于 target,那 nums[0] 和绿色这一串,从下标 1 一直到 5,每一个搭配都成立,一共 5 对,直接加进 ans,现在 ans 等于 5。下标 0 这个左端已经把它能配的都数完了,该让 l 前进一步了。
- 11一次锁定 5 对不放心可以逐对核一下:nums[0]=-7 分别加上绿色这些数,得到的和是 -13、-9、-8、-5、-4,每一个都严格小于 -2。这正是排序的好处,一次比较就锁定一整批,不用一对一对去算。
- 12和偏小:可整批数当前窗口两端是 nums[1]=-6 和 nums[5]=3,它们的和是 -3。拿它和 target=-2 比:这个和严格小于 target。有序数组里 l 和它右边每个数搭配,和都不超过这个两端和,所以也全都小于 target。
- 13ans = 9既然两端和都小于 target,那 nums[1] 和绿色这一串,从下标 2 一直到 5,每一个搭配都成立,一共 4 对,直接加进 ans,现在 ans 等于 9。下标 1 这个左端已经把它能配的都数完了,该让 l 前进一步了。
- 14一次锁定 4 对不放心可以逐对核一下:nums[1]=-6 分别加上绿色这些数,得到的和是 -8、-7、-4、-3,每一个都严格小于 -2。这正是排序的好处,一次比较就锁定一整批,不用一对一对去算。
- 15和偏大:缩右边当前窗口两端是 nums[2]=-2 和 nums[5]=3,它们的和是 1。拿它和 target=-2 比:这个和不小于 target。既然最左的 nums[2] 配上最大的 nums[5] 都到不了严格小于,别的左端更大更不行,这个右端可以整个排除。
- 16排除,r 左移两端和到不了严格小于,右端 nums[5]=3 是当前最大的数,它配上最小的左端都超标,配别的更超标,所以它不可能出现在任何合格的数对里,把它灰掉排除。右指针后退一格到 4,窗口缩小,继续看新的两端。
- 17和偏大:缩右边当前窗口两端是 nums[2]=-2 和 nums[4]=2,它们的和是 0。拿它和 target=-2 比:这个和不小于 target。既然最左的 nums[2] 配上最大的 nums[4] 都到不了严格小于,别的左端更大更不行,这个右端可以整个排除。
- 18排除,r 左移两端和到不了严格小于,右端 nums[4]=2 是当前最大的数,它配上最小的左端都超标,配别的更超标,所以它不可能出现在任何合格的数对里,把它灰掉排除。右指针后退一格到 3,窗口缩小,继续看新的两端。
- 19和偏小:可整批数当前窗口两端是 nums[2]=-2 和 nums[3]=-1,它们的和是 -3。拿它和 target=-2 比:这个和严格小于 target。有序数组里 l 和它右边每个数搭配,和都不超过这个两端和,所以也全都小于 target。
- 20ans = 10既然两端和都小于 target,那 nums[2] 和绿色这一串,从下标 3 一直到 3,每一个搭配都成立,一共 1 对,直接加进 ans,现在 ans 等于 10。下标 2 这个左端已经把它能配的都数完了,该让 l 前进一步了。
- 21一次锁定 1 对不放心可以逐对核一下:nums[2]=-2 分别加上绿色这些数,得到的和是 -3,每一个都严格小于 -2。这正是排序的好处,一次比较就锁定一整批,不用一对一对去算。
- 22停止 · ans = 10现在 l 和 r 撞到一起了,窗口里凑不出两个不同的数,再没有新的数对可数,循环结束。整个过程里每一步要么整批计数、l 前进,要么排除右端、r 后退,两个指针一共只走了一趟,又快又不重不漏。
- 23答案 = 10把三次整批计数加起来,5 对、4 对、再加 1 对,一共 10 对,这就是答案。回头看这套双指针:靠排序把数组理顺,再让两端夹逼,小了整批收、大了缩右边,时间只花在排序和这一趟扫描上,比两两枚举快得多。
⚠️ 容易写错的地方
✗ 错：不排序直接双指针
✓ 对：必须先排序再夹逼
双指针靠有序才能由两端和一次判定一整批,乱序时两端不是最小最大,整批计数的推理就不成立
✗ 错：把严格小于写成小于等于
✓ 对：和正好等于 target 的对不计入
题目要求严格小于,取等的那些下标对不算,条件写成小于等于会把和等于 target 的对错误计入,排除条件必须是 sum ≥ target
✗ 错：计数写成 r 减 l 加 1
✓ 对：一次记入的是 r 减 l 对
合格的是下标 l 与 l+1 到 r 这 r-l 个伙伴的搭配,不含 l 自己配自己,多加一会重复
✗ 错：两端和小了却去缩右边
✓ 对：和小于 target 时整批计数并让 l 右移
和已经够小,要保留右端去数更多对,该前进的是左指针;缩右边会漏掉大量合格对
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 ansC++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int countPairs(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int ans = 0;
for (int j = 0; j < nums.size(); ++j) {
int i = lower_bound(nums.begin(), nums.begin() + j, target - nums[j]) - nums.begin();
ans += i;
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int countPairs(List<Integer> nums, int target) {
Collections.sort(nums);
int ans = 0;
for (int j = 0; j < nums.size(); ++j) {
int x = nums.get(j);
int i = search(nums, target - x, j);
ans += i;
}
return ans;
}
private int search(List<Integer> nums, int x, int r) {
int l = 0;
while (l < r) {
int mid = (l + r) >> 1;
if (nums.get(mid) >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
}复杂度
时间
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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 统计和小于目标的下标对数目 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题为什么排序后能用双指针?+
排序让数组变得单调,两端分别是当前窗口的最小值和最大值。于是只看两端和就能对一整批下判断:和小于 target 时,左端配右边一整串都成立,一次数入 r 减 l 对再让左指针前进;和不小于时,最大的右端配最小左端都超标,右指针左移排除它。每个元素最多被两个指针各扫一次,总共一趟。
除了双指针还能怎么做?+
可以排序后对每个右端点做二分,数它左边有多少个数严格小于 target 减去它,这正是参考代码的写法,总复杂度也是 O(n log n)。数据规模很小的时候,直接两重循环暴力枚举所有对是 O(n 的平方),对 n 到 50 也能过,但双指针和二分更能体现思路。
复杂度是多少,瓶颈在哪?+
瓶颈是排序,O(n log n)。双指针扫描只有 O(n),所以总时间 O(n log n)。空间上除了几个指针是 O(1),若把排序内部开销算进去,C 加加 和 Java 大约 O(log n) 递归栈,Python 的 Timsort 最坏 O(n)。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 统计和小于目标的下标对数目 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。