LeetCode 986中等区间 · 双指针
区间列表的交集 图解题解
这道题到底在问什么
给定两个区间列表 A 和 B，每个列表内部都已按起点排好序、且自身区间互不重叠。返回这两个列表的交集（所有重叠区间）。
- 输入
- A = [[0,2],[5,10],[13,23],[24,25]] B = [[1,5],[8,12],[15,24],[25,26]]
- 输出
- [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
最优解：一步一步想明白
- 3核心两步：① 重叠区间 = [起点取大, 终点取小]，lo≤hi 才算数；② 终点更小的那个指针前进。
- 4开始：指针 i 指向 A 的第 0 个区间（高亮格），指针 j 指向 B 的第 0 个区间（侧栏高亮行）。答案先是空的。
- 5比较 A[0]=[0,2] 和 B[0]=[1,5]：重叠左端 lo 取两起点的大者=1，右端 hi 取两终点的小者=2。
- 6因为 lo=1 不大于 hi=2，这段 [1,2] 是真实重叠，收进答案。
- 7A[0] 的终点 2 比 B 的终点 5 小，它对后面再没贡献，所以 i 前进一格到 1。
- 8比较 A[1]=[5,10] 和 B[0]=[1,5]：重叠左端 lo 取两起点的大者=5，右端 hi 取两终点的小者=5。
- 9因为 lo=5 不大于 hi=5，这段 [5,5] 是真实重叠，收进答案。
- 10B[0] 的终点 5 比 A[1] 的终点 10 小，它对后面再没贡献，所以 j 前进一格到 1（A 的指针不动）。
- 11比较 A[1]=[5,10] 和 B[1]=[8,12]：重叠左端 lo 取两起点的大者=8，右端 hi 取两终点的小者=10。
- 12因为 lo=8 不大于 hi=10，这段 [8,10] 是真实重叠，收进答案。
- 13A[1] 的终点 10 比 B 的终点 12 小，它对后面再没贡献，所以 i 前进一格到 2。
- 14比较 A[2]=[13,23] 和 B[1]=[8,12]：重叠左端 lo 取两起点的大者=13，右端 hi 取两终点的小者=12。
- 15因为 lo=13 大于 hi=12，A[2] 和 B[1] 没有公共部分，什么都不收。
- 16B[1] 的终点 12 比 A[2] 的终点 23 小，它对后面再没贡献，所以 j 前进一格到 2（A 的指针不动）。
- 17比较 A[2]=[13,23] 和 B[2]=[15,24]：重叠左端 lo 取两起点的大者=15，右端 hi 取两终点的小者=23。
- 18因为 lo=15 不大于 hi=23，这段 [15,23] 是真实重叠，收进答案。
- 19A[2] 的终点 23 比 B 的终点 24 小，它对后面再没贡献，所以 i 前进一格到 3。
- 20比较 A[3]=[24,25] 和 B[2]=[15,24]：重叠左端 lo 取两起点的大者=24，右端 hi 取两终点的小者=24。
- 21因为 lo=24 不大于 hi=24，这段 [24,24] 是真实重叠，收进答案。
- 22B[2] 的终点 24 比 A[3] 的终点 25 小，它对后面再没贡献，所以 j 前进一格到 3（A 的指针不动）。
- 23比较 A[3]=[24,25] 和 B[3]=[25,26]：重叠左端 lo 取两起点的大者=25，右端 hi 取两终点的小者=25。
- 24因为 lo=25 不大于 hi=25，这段 [25,25] 是真实重叠，收进答案。
- 25A[3] 的终点 25 比 B 的终点 26 小，它对后面再没贡献，所以 i 前进一格到 4。
- 26其中一个列表的指针已走到头，循环结束。沿途收集的这 6 段就是两个列表的全部交集。
⚠️ 容易写错的地方
✗ 错：用 lo<hi 判断有没有重叠
✓ 对：用 lo<=hi
两区间在单个端点相接（如 [5,10] 与 [1,5]）时 lo=hi=5，是合法交集 [5,5]，漏了 = 错
✗ 错：重叠时把整个 A[i] 或 B[j] 收进答案
✓ 对：只收 [max(起), min(终)]
交集是两区间的公共部分，不是其中某一个整段
✗ 错：前进时凭起点大小挪指针
✓ 对：凭终点大小：终点小的先走
终点小的区间对后面的区间再无贡献，留着终点大的去和下一个比才不漏
完整代码（Python / C++ / Java）
Python
def intervalIntersection(A, B):
res = []
i = j = 0
while i < len(A) and j < len(B):
lo = max(A[i][0], B[j][0]) # 起点取大
hi = min(A[i][1], B[j][1]) # 终点取小
if lo <= hi: # 有重叠
res.append([lo, hi])
if A[i][1] < B[j][1]: # 终点小者前进
i += 1
else:
j += 1
return resC++
vector<vector<int>> intervalIntersection(
vector<vector<int>>& A, vector<vector<int>>& B){
vector<vector<int>> res;
int i = 0, j = 0;
while (i < A.size() && j < B.size()) {
int lo = max(A[i][0], B[j][0]);
int hi = min(A[i][1], B[j][1]);
if (lo <= hi) res.push_back({lo, hi});
if (A[i][1] < B[j][1]) i++;
else j++;
}
return res;
}Java
public int[][] intervalIntersection(int[][] A, int[][] B) {
List<int[]> res = new ArrayList<>();
int i = 0, j = 0;
while (i < A.length && j < B.length) {
int lo = Math.max(A[i][0], B[j][0]);
int hi = Math.min(A[i][1], B[j][1]);
if (lo <= hi) res.add(new int[]{lo, hi});
if (A[i][1] < B[j][1]) i++;
else j++;
}
return res.toArray(new int[0][]);
}复杂度
时间
O(m+n)
i、j 各自只往后走，两个列表合起来共 m+n 个区间，每个最多被看一次
空间
O(1)
除答案数组外只用 i、j 两个指针，不开额外结构（答案本身不计入）
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 区间列表的交集 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么这道题双指针都不用回退？+
因为 A、B 各自按起点有序且内部不重叠。指针只需单向前进，终点小的先走，整体是一趟 O(m+n) 的归并式扫描。
两区间只在一个端点相接（如 [5,10] 和 [1,5]）算不算交集？+
算。lo=hi=5，交集是单点区间 [5,5]。所以判定条件必须是 lo<=hi 而不是 lo<hi。
如果某个列表为空，结果是什么？+
返回空列表。while 条件 i<len(A) and j<len(B) 一开始就不成立，直接返回空答案。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 区间列表的交集 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。