刷算法题的人都懂LeetCode 611 “有效三角形的个数”看起来是个简单题但真正动手写的时候边界条件、双指针移动逻辑、计数方式每一个点都能揪出一堆细节。尤其是第一次接触双指针思路的人很容易写出一个“能跑但超时”的暴力版本或者写出了一个双指针但计数方式完全不对。这里我想把这道题从题目本身开始拆一直到双指针的每一步推导、Python 代码实现、以及我在刷题和面试中踩过的各种坑一次性讲透。1. 题目拆解三角形判定与暴力法的瓶颈1.1 三角形判定到底在判什么先回到最早学几何的时候三条边能组成一个三角形需要满足“任意两边之和大于第三边”。也就是说如果三条边长度是 a、b、c必须同时满足 a b c、a c b、b c a。放到编程题里很多人第一反应是把三条判断都写进去。但有一个关键优化如果先把三条边排序让 a b c那么只需要判断 a b c 这一条就够了。为什么因为 c 已经是最大的那条边了a c b 和 b c a 在这种情况下天然成立。一个正数加上另一个正数肯定大于等于它们中的任何一个而 c 本身就比 a 和 b 都大所以 a c 一定大于 bb c 也一定大于 a。唯一需要担心的组合就是两条短边之和能不能压过最长边。这个“排序后只判断最大边”的思路就是双指针解法的最底层依据。1.2 暴力做法为什么过不了如果看到这道题就直接写三层循环枚举所有三元组 (i, j, k)对每个组合做一次判断代码确实很直观十来行就能写完。但问题也很明显数组长度一上来就完蛋。假设数组长度是 n三层循环的复杂度是 O(n³)。LeetCode 上的数据范围是数组长度不超过 1000最坏情况需要遍历 1000³ 10 亿量级的组合数在 Python 这种解释型语言里就是妥妥的超时。哪怕用 C1e9 的枚举量也接近时间极限了。暴力法唯一的价值就是用来验证小数据规模下的答案是否正确比如写一个暴力版本和一个优化版本在小数组上跑一下对比结果可以快速确认优化版本没有改错逻辑。这个方法在实际刷题中真的很好用特别是针对这种计数类题目后面我会再提。1.3 排序带来的关键转变既然暴力法不行就得想办法减少无效枚举。很自然的想法是先排序。排序在这里不是单纯为了“有序”而是为了把三角形的判定条件从“三方互相制约”变成“单向制约”。排序后我们可以固定最大边然后在前面的子数组中找有多少对短边满足两数之和大于最大边。这就把“三角形计数”转化成了“两数之和”的变形问题。双指针本质上就是一个在有序数组中寻找满足某种大小关系的数对的工具而这道题恰好完美适配这个工具。2. 双指针解法的核心思路与推导2.1 固定最长边让“有效”条件变成一堆组合的公共条件双指针的第一步是枚举最长边。假设排序后的数组是 nums我们用下标 k 表示最长边的位置那两条短边只能从下标 0 到 k-1 中选。为什么固定最长边有用因为三角形判定条件 a b c 中如果把 c 固定下来我们只需要在左边找满足 nums[i] nums[j] nums[k] 的 (i, j) 数对。如果 c 值不变那么对于同一个 j随着 i 增大两个数的和会增大更容易满足条件。还有一个更重要的性质排序后数组是递增的所以当 nums[i] nums[j] nums[k] 成立时如果保持 j 不变把 i 换成 i1、i2 一直到 j-1这些数都比 nums[i] 大所以它们的和也一定大于 nums[k]。换句话说一旦找到第一个满足条件的 i就能一次性得到 j - i 个有效组合不用再一个个试。这个批量计数的能力正是双指针从 O(n³) 降到 O(n²) 的核心原因。2.2 双指针的移动规则与计数原理具体实现的时候对于每一个固定的 k在 [0, k-1] 区间内设置两个指针 i 和 j初始 i 0j k-1。然后循环执行以下判断如果 nums[i] nums[j] nums[k]说明从 i 到 j-1 的任意一个数作为左短边和 nums[j]、nums[k] 组合都能构成三角形。这次能满足的条件组合数量为 j - i。统计完之后j 向左移动一位j - 1因为 nums[j] 这个最大短边已经统计完了要缩小右边界尝试更小的最大短边。如果 nums[i] nums[j] nums[k]说明左短边太小了连当前最大的右短边都带不动那就更不可能和其他更小的右短边组合成功了。所以 i 向右移动一位i 1增大左短边再判断。循环结束的条件是 i j因为至少要两条不同的短边位置不能重叠。这个移动规则的每一步都排除了一批必然无效的组合而且保证不会漏掉有效的组合。我刚开始学的时候一直担心会不会漏解后来想明白了一个道理双指针的每一步移动都是基于当前已经确定的顺序关系来做剪枝而不是盲目跳过。i 和 j 交替移动实际上是枚举了所有可能的 (i, j) 组合但通过排序后的单调性把大量判断压缩成了 O(n) 次移动。2.3 一个例子走一遍全流程拿一个具体例子来验证。假设数组是 [2, 2, 3, 4]排序后保持不变我们要统计能组成的三角形数量。枚举 k 3nums[3] 4i 0j 2nums[0] nums[2] 2 3 5 4满足条件计数增加 j - i 2 - 0 2也就是 (2, 3, 4) 和 (2, 3, 4)这两个组合对应的是两个 2 分别与 3、4 组合。然后 j 左移变成 1。此时 i 0j 1nums[0] nums[1] 2 2 4不大于 4不满足。注意这里边界条件是严格大于不能取等号。于是 i 右移变成 1。i 1j 1i j循环结束。k 2nums[2] 3i 0j 1nums[0] nums[1] 2 2 4 3计数增加 j - i 1对应 (2, 2, 3)。j 左移变成 0。i j循环结束。k 1nums[1] 2i 0j 0不满足 i j直接跳过。总计 2 1 3 个三角形。等一下这里有个问题。第一次枚举 k 3 的时候计数加 2分别是 (2, 2, 3, 4) 中的哪两组我重新整理一下nums 是 [2, 2, 3, 4]下标 0 的 2 和下标 1 的 2 是两个不同的元素。k3 固定最长边 4left 指针 i0 指向第一个 2j2 指向 3组合 (nums[0]2, nums[2]3, nums[3]4) 和 (nums[1]2, nums[2]3, nums[3]4) 都是有效的。注意计数时 j - i 2正好囊括了下标 0 和 1 两个“2”。这个细节说明双指针的批量计数不是粗略估算它精确地统计了每个可用的左指针位置。这个例子最终答案是 3和暴力枚举的结果一致。过程走完整个双指针的流程就清楚了。3. Python 实现与代码细节3.1 完整代码与逐行注释直接给出完整的 Python 实现下面这段代码是我实测过、可以稳定通过的版本def triangle_number(nums): nums.sort() n len(nums) ans 0 for k in range(2, n): # 枚举最长边的位置至少要有三个数 i 0 j k - 1 while i j: if nums[i] nums[j] nums[k]: ans j - i # 从 i 到 j-1 的所有位置都能和 j、k 组成三角形 j - 1 # 当前右端 j 已经统计完尝试更小的最大短边 else: i 1 # 左端太小需要增大左端才有可能满足条件 return ans这段代码只有十几行但信息密度很高。外层循环 k 从 2 开始因为至少要三个数才能构成三角形内层双指针在 [0, k-1] 区间内寻找所有满足 nums[i] nums[j] nums[k] 的数对。在 if 分支里ans j - i 这里最容易出错。为什么不是 ans 1因为当 nums[i] nums[j] nums[k] 时由于数组递增nums[i1]、nums[i2] 一直到 nums[j-1] 都比 nums[i] 大所以它们与 nums[j]、nums[k] 的组合也一定满足条件。一次统计 j - i 个组合而不是只统计一个这才是双指针效率高的原因。在 else 分支里nums[i] nums[j] nums[k] 时如果左指针 i 不动右指针 j 无论怎么左移两数之和只会更小更不可能满足条件所以只能让 i 右移。同理这个剪枝也是一次性排除了所有与当前 i 相关的无效组合。3.2 边界处理的几个隐藏考点第一个边界最短的 i 从 0 开始j 从 k-1 开始这个没有问题。但外层循环的 k 到底从几开始如果从 1 开始那么 j 初始是 0i 也是 0i j 不成立循环直接不执行。所以写 k 从 2 开始更语义化也省去一次无意义的循环。第二个边界while i j 而不是 while i j。因为两条短边不能是同一个元素。排序后的数组里可能出现相同值的不同元素但那是两个不同的下标只要下标不同就可以用。i j 天然保证了两条短边是不同的下标。有些题目里允许重复使用同一个元素但三角形题不允许三条边来自同一个元素所以必须是 i j。第三个边界三角形判定是严格不等式 nums[i] nums[j] nums[k]不能写成 。三条边长度相等的情况要特别注意比如三条边都是 22 2 2 成立可以构成等边三角形。但如果最大边是 4短边是 2 和 22 2 4 不满足严格大于不能构成三角形。这就是为什么例子里最后 (2, 2, 4) 没有被计入。第四个边界数组元素可能是 0。0 不能出现在三角形里因为 0 任意正数 那个正数不可能严格大于最大边。但双指针的逻辑天然排除了这种情况0 作为左指针时nums[i] nums[j] 很可能小于等于 nums[k]i 会继续右移不会把 0 统计进去。所以不需要在代码里专门跳过 0 值。3.3 复杂度分析为什么是 O(n²)从代码结构看外层循环 n 次内层 while 循环每次最多移动 i 或 j 一次而 i 和 j 的总移动次数不超过区间长度所以内层是 O(n)。总复杂度 O(n²)。空间复杂度 O(1)排序用的是原地 sort()。有人可能会想外层 n 次内层也是 n 的量级那不就是 O(n²)是的没有额外的 log n因为内层的每一步都是 O(1) 的数组访问和比较没有嵌套的额外循环。对比三个版本的差异会更直观实现方式时间复杂度空间复杂度能否通过 LeetCode三层暴力枚举O(n³)O(1)数据大时超时二分查找优化O(n² log n)O(1)能通过但略慢双指针O(n²)O(1)能通过速度最优二分查找版本是另一种常见思路固定最长边和一条短边在剩余区间中二分查找满足条件的第三条边。这个思路也能过但多一个 log n 因子。双指针的 O(n²) 在 n1000 时大概需要 100 万次操作在 Python 中零点几秒就能跑完非常轻松。4. 刷题现场容易踩的坑与排查技巧4.1 边界条件写错的三种典型情况第一种j 的初始值写成了 k也就是让最长边参与双指针统计然后判断条件变成 nums[i] nums[j] nums[k]此时 i 和 j 里 j 可能等于 k统计出的组合实际上用了同一个元素三次。这种情况在某些测试用例下可能碰巧不会出错但遇到数组长度等于 3 的用例时一定会出问题。典型表现是答案偏大因为把“使用三个不同下标”的错误组合也算进去了。第二种内层循环结束时忘记重置 i 的值。外层每枚举一个新的 ki 必须重新从 0 开始。如果在上一次循环结束后 i 已经移到了某个较大的位置下一次外层循环直接使用这个 i就会漏掉很多组合。这种 bug 比较隐蔽因为有时碰巧 i 还能跑到正确的位置附近导致小数据测试不报错大数据测试结果不对。第三种条件写成 。这个前面已经举例了。线段长度恰好等于另一边时不能组成三角形这是定义必须严格要求严格大于。如果这个条件错了会造成略微多计数尤其是数组中存在大量重复值的时候误差会被放大测试用例一多特别明显。我排查这类问题常用的方法是构造一个超小数组比如长度为 3 的 [1, 2, 3] 或 [2, 2, 4]手动走一遍代码逻辑看每一步的 i、j、k 取什么值再和一个绝对正确但低效的暴力解法对照。建议每个刷题的人都在本地维护一个暴力版函数用它做交叉验证尤其适合这种计数类题目。把暴力版写成嵌套循环跑一遍结果再用优化版跑同样的输入两边答案不一致就说明优化逻辑里有细微 bug。4.2 重复元素到底要不要特殊处理这道题有一个比较迷惑人的地方数组中如果有重复元素比如 [2, 2, 3, 4]两个 2 是两条不同的边组合 (2, 2, 3) 和 (2, 2, 4) 都算有效组合。双指针的 i 和 j 是按数组下标移动的所以两个值相同的 2 只要下标不同就会被当成两个独立的元素统计。不需要额外进行“去重”操作也不需要像三数之和那样跳过重复的起始位置。这是计数类双指针和求和类双指针的重要区别。三数之和要求不重复三元组必须跳过相邻相同元素有效三角形个数要求统计所有组合重复值是不同边必须全部计入。如果在这里画蛇添足地去重反而会把正确答案改错。我见过不少人在这一题上翻车就是因为套用了“三数之和”的模板在循环里加了个 while nums[i] nums[i-1]: i 1 之类的去重逻辑。结果每次遇到重复值都跳过计数就少了。所以记住这道题不要主动去重除非题目明确要求输出唯一的组合方式。4.3 面试官追问还能不能更快这题能不能优化到 O(n log n)理论上可以但没必要。当前双指针 O(n²) 已经是最优的时间复杂度级别要想突破这个下界需要用到更复杂的几何性质或组合数学面试场景下基本不会要求。面试官更可能追问的是如果数组长度变成 10 的 5 次方暴力 O(n²) 也扛不住怎么办。这时候可以思考两个方向一是如果三角形边长有上限比如边长不超过某个值可以用计数数组或者树状数组维护边长的频次分布快速统计合法组合二是如果只要求输出三角形个数而不是具体的组合可以考虑结合前缀和优化。但这些属于扩展思考题真正刷题和面试时掌握 O(n²) 双指针版本通常就足够应付了。我做面试复盘的时候经常被问到的一个角度是“你能不能讲清楚为什么 i 移动是 1而不是 j 移动”这个问题的核心在于理解双指针的单调性。当 nums[i] nums[j] nums[k] 时问题出在左端值太小。左边的值直接决定了和能不能大于最大边因此只能增大左端相反如果 nums[i] nums[j] nums[k]说明右端作为“次长边”对组合有效此时可以批量计数然后右端左移寻找次长边更小的组合。这个逻辑听起来简单但能在面试中清晰讲出来的候选者往往能把整个思路理顺。5. 同类题目的迁移与技巧总结5.1 双指针套路的一道通吃链有效三角形个数是双指针思想里的典型应用它和很多经典题目共享同一个底层模型两数之和 II已排序固定一个端双指针找两数之和等于目标值的下标。三数之和先固定第一个数剩余部分用双指针找两数之和。最接近的三数之和思路类似只是把“等于”改成“最接近”。四数之和多固定一层再用双指针处理剩余部分。这一串题目都遵循一个模式排序固定一个或两个数再对剩余区间用左右指针维护单调性将 O(n²) 或 O(n³) 的枚举降到低一阶的复杂度。有效三角形个数的特殊之处在于它的“目标值”不是固定的而是动态变化的。每次外层枚举 k目标值就是 nums[k]。这提醒我们很多双指针题目中目标值可以是一个随着外层循环不断变化的量只要有序性保持成立双指针的思路依然能走到最优复杂度。5.2 遇到新题怎么快速识别双指针模型如果看到一道题数组需要找两个或多个元素的组合并且满足某种大小关系同时数组排序后被搜索区间呈现单调关系就可以优先考虑双指针。判断依据大概可以归纳为三点组合数量不要求唯一只统计个数或是否存在。如果要求输出所有不重复组合要用去重技巧双指针的方向要做调整。有序数组上的单调性关系。如果数组是乱序先排序是否能保持答案不变。有效三角形个数依赖边长大小关系排序不影响三角形判定所以可以排序。如果题目依赖原始顺序双指针就不适用。能否通过左右指针移动排除大块候选解。双指针的剪枝效力来自有序性每次移动都能排除一个区间内的大量组合。如果移动不能形成批量排除那基本不是双指针题而是更通用的回溯题。这几个判断点可以帮助快速过滤一道新题适不适合用双指针。另外双指针代码通常很短但很考验对单调性和边界条件的理解。建议刷这道题时不要只看别人的题解然后就过了一定要手动打几组测试用例把 i、j、k 的变化过程画出来多走两遍。我自己的感受是这种“手动跟踪变量动画”的学习方法比看十篇题解都有效果尤其是对双指针这种依赖过程正确性的算法。关于本题的实际应用场景很多人觉得算法题只在面试和竞赛中有意义。但双指针这种在有序区间上维护单调关系的思路在实际工程中也有对应场景比如分析一段时间序列上的组合统计、合并有序区间、计算满足某种统计条件的数据范围等。虽然不会真的拿这套模板直接复制到项目里但思路本身是有通用价值的。最后再分享一个小经验如果你在本地跑代码时发现答案总比预期多几个大概率是边界条件把“边长相等”的情况误判成有效如果答案总比预期少几个大概率是某个连续区间的某个边界位置被跳过了。多在这两个方向自查比盲目调代码效率高得多。