直接进入正题。区间列表的交集这道题在力扣上属于“双指针”标签下的经典题看起来很简单——给你两个排好序的区间列表求它们的交集。但真上手写的时候很多人都会在指针移动、边界判断上栽跟头。我最初刷这道题时第一反应是“两层循环暴力比较不就行了”结果一写就发现时间复杂度直接上到O(n*m)数据量一大立刻脸红。后来老老实实推了一遍双指针的移动逻辑才发现这题其实是用最小代价解决“两个有序序列对齐”问题的绝佳范例。这篇文章不打算只贴一段代码了事我会把从思路推导、代码实现到变体和工程落地的完整链条都掰开揉碎讲一遍顺便把我踩过的坑一并交代清楚。1. 区间列表的交集到底在考什么1.1 题目背景与核心需求解析题目本身一句话就能说清楚给定两个由若干闭区间组成的列表每个区间列表内的区间已经按起点从小到大排好序要求返回这两个列表的交集。所谓闭区间就是说区间的左右端点都包含在内这一点在判断相交时至关重要。举个例子第一个列表是[[0,2],[5,10],[13,23],[24,25]]第二个列表是[[1,5],[8,12],[15,24],[25,26]]那这两个列表的交集就是[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]。这里有一个非常容易忽略的细节两个区间端点重合也算交集。也就是说[5,10]和[1,5]交集是[5,5]不能因为区间长度为0就丢掉。这个点和后面写代码时的判断逻辑直接相关。这道题表面上叫“双指针”实际上考察的是你如何利用“有序”这个前提条件把两两配对比较的次数从 O(n*m) 降下来。很多第一次接触这道题的人会本能地选择暴力遍历这没有错但面试官接下来必然会追问一句“如果两个列表都很大有没有办法一次扫描完成”这时候双指针的思路就呼之欲出了。1.2 为什么双指针是正解而非暴力遍历暴力的思路很简单枚举第一个列表里的每个区间再枚举第二个列表里的每个区间判断二者是否相交。伪代码大概长这样for a in list1: for b in list2: if a和b相交: 记录交集这种做法在列表很短的时候完全可行但一旦数据规模上来n和m都是十万量级O(n*m) 就是天文数字。而且你仔细想一下会发现暴力解法浪费了一个极其重要的信息——两个列表都是有序的。有序意味着什么呢意味着如果第一个列表的当前区间在第二个列表的当前区间的左边那么第一个列表当前区间无论如何都不可能和第二个列表后面的任何区间相交。因为第二个列表是递增的后面的区间起点只会更大、离得更远。这个观察就是双指针移动的全部依据每次比较两个当前区间后只需要移动“更靠左”的那个区间所在的指针因为那个区间已经“用完”了。打个比方就像两个人各自手里有一叠按时间排列的日程表你要找出两人都有空的时段。你每次只看两张表上最靠前的日程肯定只需要翻“结束得比较早”的那一叠因为那个人的这个日程之后再也没有机会和另一个人的当前日程重叠了。双指针的本质就是把这种直觉形式化成算法。1.3 两个前提条件决定了整个解法走向要使用双指针两个前提条件一个都不能少列表必须有序。而且这里的有序是“按区间起点排序”。如果题目不给这个条件你第一步要做的就是自己排序。用Arrays.sort或者sort()按interval[0]升序排一遍即可排序的时间复杂度是 O(n log n m log m)后续双指针扫描就能回到线性时间。区间必须是闭区间。如果是开区间比如(0,2)和(2,4)两者的交集为空和闭区间情况下能得到[2,2]完全不同。所以拿到题目先确认区间的开闭性这直接决定比较逻辑中的等号写法。力扣这道题明确是闭区间所以使用比较针对准确解。只要这两个条件成立整个算法就可以压缩成一次线性扫描两个指针分别从头走到尾每一步的操作都是 O(1) 的计算没有任何回溯和重复遍历。2. 双指针算法的完整推导2.1 每一趟比较究竟发生了什么假设两个指针分别叫i和j初始都指向各自列表的第一个区间。每一轮循环我们都拿list1[i]和list2[j]这两个区间做一次“对齐操作”。对齐的结果有三种可能相交、左边不相交、右边不相交。如何判断是否相交数学上最简洁的方法是计算两个区间的重叠部分取两个区间左端点的较大值作为重叠部分的左端点取两个区间右端点的较小值作为重叠部分的右端点。如果左端点小于等于右端点说明确实存在交集。这个逻辑写出来只有一个公式left max(start1, start2) right min(end1, end2) 如果 left right就存在交集 [left, right]很多初学者在看代码时最困惑的就是这个max和min的来源。其实不需要背画个坐标轴两个区间的重叠部分一定是被“右侧较晚开始”的左端点和“左侧较早结束”的右端点夹出来的。如果较晚开始的左端点大于较早结束的右端点说明这两个区间中间有缝隙根本碰不到。这个判断方法不仅适用于这道题区间合并、区间覆盖、会议室安排等一系列区间类问题都会反复用到。建议直接把这套逻辑记成肌肉记忆。2.2 指针移动规律的真实逻辑确定了当前两个区间的关系之后最关键的问题来了本轮比较结束后到底移动哪个指针规则也很简单谁先结束谁移动。也就是说比较list1[i]的终点和list2[j]的终点哪个终点数值更小对应的指针就往后走一步。如果两者终点相等两个指针都可以往后走代码里一般移动i也可以都移动但必须保证不会死循环。为什么这么移动因为一个区间的“有效配对范围”取决于它的右端点。假设list1[i]的右端点是 5list2[j]的右端点是 10那么当i和j比较完之后list1[i]就再也不可能与list2[j]后面的任何区间相交了——后面的区间起始点至少是list2[j1].start而这个值大于等于 10显然不可能与结束于 5 的区间有重叠。因此list1[i]已经完成了它的历史使命应该被丢弃指针i前进。反过来如果list1[i]的右端点是 10list2[j]的右端点是 5那么list2[j]就退役了移动j。这种“一条路走到黑谁结束谁离开”的模式正是双指针高效的原因——每个区间最多被处理两次一次用来计算交集一次用来决定移动方向。2.3 核心代码实现含Java/Python版本思路理顺了代码其实非常短。先上 Java 版本最直观public int[][] intervalIntersection(int[][] firstList, int[][] secondList) { int i 0, j 0; Listint[] result new ArrayList(); while (i firstList.length j secondList.length) { int start Math.max(firstList[i][0], secondList[j][0]); int end Math.min(firstList[i][1], secondList[j][1]); if (start end) { result.add(new int[]{start, end}); } // 关键谁先结束谁移动 if (firstList[i][1] secondList[j][1]) { i; } else { j; } } return result.toArray(new int[result.size()][]); }Python 版本几乎可以逐行对照def intervalIntersection(firstList, secondList): i, j 0, 0 result [] while i len(firstList) and j len(secondList): start max(firstList[i][0], secondList[j][0]) end min(firstList[i][1], secondList[j][1]) if start end: result.append([start, end]) if firstList[i][1] secondList[j][1]: i 1 else: j 1 return result代码逻辑的妙处在于你不用区分当前位置到底是“相交”、“A在左”还是“B在左”只需要统一用start end判断是否记录再用右端点大小关系决定移动对象。每一次循环都推进至少一个指针所以循环次数最多是len(A) len(B)绝对不会出现重复比较。3. 复杂度分析与边界条件全解3.1 时间复杂度和空间复杂度怎么算双指针解法的时间复杂度是 O(n m)其中 n 和 m 分别是两个列表的长度。原因很简单每个指针从头走到尾最多移动n次和m次没有任何指针会回溯。这里的“线性时间”是相对于暴力法的 O(n*m) 来说质的飞跃。空间复杂度方面如果不考虑存储结果集的数组算法的额外空间是 O(1)只用了两个指针和几个临时变量。结果集在最坏情况下有多长答案是 O(n m)例如两个列表都是[[1,2],[3,4],[5,6]...]且完全相同每个区间都能配对出交集。所以整体的空间复杂度是 O(n m)但这是输出本身的占用不能算作算法引入的额外开销。很多人在分析这道题复杂度时会把“结果集长度”和“额外空间”混为一谈面试时建议主动说明一句“如果不把输出结果算在内额外空间是 O(1)”这能体现出你对空间复杂度的理解不是机械背结论。3.2 面试里最容易踩的五个边界坑这套代码表面上只有十几行坑点全藏在边界条件里。我总结了自己和身边人踩过的高频坑按照出现概率排序第一个坑区间完全包含时的指针移动。比如A [1,10]B [2,3]。按代码逻辑本轮得到交集[2,3]然后因为A的右端点 10 大于B的右端点 3所以移动j。下一轮B [4,5]依然与A [1,10]相交得到[4,5]。这样 A 这个大区间会一直留在场上直到被 B 的整个列表耗尽。很多人第一次看代码时会担心“A 是不是漏了”实际上因为 A 的右端点迟迟不退役算法会把它和 B 的每一个区间都尝试配对这正是我们需要的效果。但是如果移动方向写反了比如右端点相等时移动的是j而不是i在某些情况下结果仍然正确但代码逻辑的对称性就破坏了调试时容易出错。建议固定写法小于移动i否则移动j。第二个坑端点相接算不算交集。闭区间下[1,2]和[2,3]的交集必须输出[2,2]。因为start max(1, 2) 2end min(2, 3) 2满足2 2记录。如果把判断写成start end这个答案就会被丢掉。这个错误非常隐蔽因为样例数据往往不会覆盖到端点相接的情况很多人在自以为“AC”的状态下就被挂掉了。第三个坑空列表输入。如果firstList或secondList是空数组while循环条件直接不满足返回空结果。这个没问题。但有一种特殊情况列表不为空但里面的区间是空的比如[5,3]这在数学上不合法不过题目约定输入的区间都是合法的所以不用处理。但如果自己写工具函数建议加一层防御判断。第四个坑结果集的类型转换。Java 中Listint[]转int[][]时要调用toArray(new int[0][])或toArray(new int[result.size()][])如果直接使用toArray()返回的是Object[]编译都过不了。Python 中没有这个问题但要注意如果firstList是元组列表返回的是新列表而不是原列表的引用避免后续修改互相干扰。第五个坑while 循环条件写成i firstList.length。这是典型的“多走一步”错误数组下标越界直接崩溃。while的条件必须是i length j length因为当i指向最后一个区间时处理完这一轮后可能自增到length此时应该退出循环而不是继续访问。4. 高频变体与排坑实录4.1 经典变体区间合并、插入区间、区间覆盖区间列表的交集只是区间问题家族里的一环。刷完这道题之后下面几个变体你几乎一定会遇到而且完全可以套用今天讲的这套“取交集用 max/min决定移动看右端点”的思路。变体一区间合并。给定一个可能有重叠的区间列表要求合并所有重叠区间输出不重叠的列表。核心逻辑是先按起点排序然后遍历时维护一个“当前合并区间”每来一个新区间如果它的起点小于等于当前区间的终点说明可以合并更新终点为两者较大值否则把当前区间加入结果切换到新区间。这里的判断条件和双指针解题中的start end几乎是同一个影子。变体二插入区间。给一个已经按起点排序且互不重叠的区间列表再给一个新的区间要求插入后仍然有序且合并重叠部分。常规做法是分段处理把新区间之前完全不重叠的部分先加入结果然后处理所有与新区间重叠的区间更新新区间的左右端点最后加入剩余部分。这个变体用到的关键判断仍然是“新区间的 end 是否大于等于某个区间的 start”。变体三区间覆盖长度。求一个区间列表在给定目标区间内的覆盖长度总和。需要先排序然后累加有效覆盖长度同时注意合并重叠部分防止重复计数。这道题和交集的共同点在于是否重叠的判断统一抽象为max(start1, start2) min(end1, end2)。我当时刷完“区间列表的交集”紧接着做“区间合并”明显能感觉到思路迁移的顺畅感——因为它们共享同一套区间相交的判定数学模型真正需要思考的只是各自的业务目标不同。4.2 实战踩坑记录与排查思路这里记录两个我实际调试时遇到的真实问题给后来者一个排查的参照。问题一为什么我的结果总是少了“端点相接”的交集症状样例测试全过但提交后被隐藏用例挂掉。排查过程先用笔在纸上画几个端点相接的区间比如[1,3]和[3,5]手动演算一遍得到交集[3,3]然后用我的代码跑发现结果确实没有。定位到if (start end)被我写成了if (start end)改回来就过了。这个案例提醒我凡是处理闭区间的问题第一眼检查和。问题二为什么遇到两个列表长度悬殊时会出现结果缺失症状A 列表长度很大B 列表长度很小结果只输出了一部分。排查过程用简单用例逐步模拟指针移动发现问题出在我把指针移动条件写成了if (firstList[i][1] secondList[j][1]) i; else j;当两端点相等时两个指针只移动一个看似没问题但在某些连续等值区间的情况下会提前丢失配对机会。改成小于号移动i大于等于移动j结果就正确了。实际上两端点相等时移动哪一个理论上都能得到正确结果前提是逻辑自洽但为了避免脑内模拟时出错我建议统一用if (end1 end2) i; else j;这样“谁先结束谁走”的语义最清晰。问题三用 Python 写时结果列表顺序不对。症状输出的交集区间顺序和预期不一致仔细一看发现是输入列表没有排序。题目说明里明明写了有序但我自己造测试数据时没有遵守导致算法前提被破坏。单步跟踪半天发现逻辑没问题问题出在测试输入本身。排查结论使用双指针算法前务必确认输入真的有序。5. 从刷题到工程落地5.1 这类题在真实场景里用在哪如果你以为这道题只活在面试题里那就低估了区间运算的价值。实际工程里几个非常典型的场景都需要这套算法作为底层支撑第一个场景是会议室/工位预约系统的冲突检测。当用户提交一个新的预约时间系统需要判断这段时间是否与已有预约冲突。如果把所有已约时间区间看成一个列表新预约看成另一个列表判断是否有交集就是区间列表求交问题的一个特例。尤其是当系统需要同时加载多个用户的预约表来寻找一个所有人都有空的会议时间时本质就是多个有序区间列表求共同交集双指针的思想可以扩展成 K 指针版本。第二个场景是数据库时间范围的索引合并。在查询优化中有时会把查询条件的时间范围拆成多个子区间与索引已有的时间分区做匹配。有序区间之间的交集运算尤其是多路归并场景底层就是这种双指针/多指针的线性扫描。这和归并排序的合并阶段在精神上是完全一致的都是利用有序性避免重复扫描。第三个场景是网络数据包处理中的范围匹配。例如防火墙规则里的端口区间、IP 地址段当一组新规则和一组已有规则需要做覆盖重叠分析避免规则冲突或冗余时区间求交集就是最基础的原语。我自己在实际项目中就遇到过类似需求一个配置系统里要合并多个来源的 IP 段最终使用的就是“排序线性扫描”的区间合并方案和今天这道题的解题框架是同构的。5.2 如果列表没有排序怎么办工程数据很少会像力扣题目那样已经排好序。如果拿到的是无序区间列表有两个选择。第一个选择是直接排序然后套用双指针解法。排序的时间复杂度是 O(n log n m log m)在数据量不算太大的情况下完全够用。需要注意自定义排序的写法Java 里注意溢出陷阱(a, b) - a[0] - b[0]在大数相减时可能溢出建议用Integer.compare或Comparator.comparingInt。第二个选择是用哈希表做预处理。如果区间端点的取值范围很小比如都是 0 到 100 之间的整数可以用差分数组标记两个列表各自占用的端点然后一次扫描找出被两个列表同时标记的位置合并成区间。这种方案本质上是把区间映射成离散点在端点数量有限时效率极高但端点值很大的时候不适用。大多数情况下我推荐直接排序因为代码更通用、语义更清晰。5.3 大数据量下的优化思路如果两个列表都极其庞大比如各有上亿个区间一次全量加载进内存是不现实的。这时候有几个优化方向分块流式处理。把区间列表按块读入内存每次处理一块记录当前两块之间的交界状态用有限的缓冲区完成全量计算。这相当于把双指针算法改造成外部归并的形式在数据库中尤其常用。二分加速。如果其中一个列表比较短可以用二分查找定位到可能与当前区间相交的起始位置跳过完全不可能相交的前半段。具体来说对于当前区间[s, e]只需要在另一个列表中从起点小于等于e的第一个区间开始检查即可。这种优化能把某些场景下的时间复杂度再压低一个对数级别。多线程并行分治。如果两个列表都是有序的可以把其中一个列表按照区间范围切分成多个子段每个子段交给一个线程与另一个列表做子集交集运算最后把结果按顺序合并。切分时注意子段之间不需要重叠因为有序保证了不同子段的交集体现在最终结果上天然有序合并起来非常干净。这些优化手段距离面试题较远但在真实生产环境中数据规模会逼着你往这个方向想。理解了基础双指针的本质之后这些扩展方案反而更容易看懂因为你已经清楚“算法瓶颈在哪儿”了。6. 几道同源题目的迁移思路很多人刷题有个困惑题目刷了就忘换个皮就不认识了。其实区间类问题特别适合用来训练“题目迁移”的能力因为它们变化的核心都围绕同一个交集判断公式。建议按这个顺序去刷迁移题目先吃透区间列表的交集本文题目把双指针移动的语义理解到本能层面。再做区间合并感受同一个判定公式在“合并”目标下如何使用。接着做插入区间体会“与新区间重叠的部分全部吸收”这个操作本质还是max/min判断与区间端点更新。最后做区间覆盖长度把“是否重叠”的应用从判断升级到数值计算。我在刷完这四道题后发现区间问题的难点从来不在“会不会判断相交”而在“判断之后如何根据业务目标处理”而这恰恰是面试官真正想考察的分析能力。把注意力放在这上面比多刷一百道不相关题目有效得多。再提一个很多人忽视的细节区间求交的编码实现中尽量不要在一次循环里同时移动两个指针除非你能明确说出这样做的理论依据。保守的“一次只移动一个指针”策略虽然循环次数可能多一些但最不容易出逻辑错误调试成本最低。对于工程代码而言稳定正确永远优先于微小的性能差异。如果这是你第一次接触双指针题目我的建议是把本文的 Java 代码亲手敲一遍然后用文章里的边界用例逐一测试再尝试用 Python 重写一遍。两种语言的切换能帮你把“逻辑”和“语法”分离开来真正内化这套算法思想。后续如果能坚持把变体题目刷完你对区间操作的理解会进入一个完全不同的层次。