LeetCode 611有效三角形个数：排序+双指针最优解与面试要点

面试里有一类题特别有意思题面看起来像小学数学实际做起来却能把排序、双指针、边界处理全考一遍。LeetCode 611“有效三角形的个数”就是典型。很多人以为只要会“两边之和大于第三边”这道题就结束了结果真到了面试现场要么三层循环超时要么双指针写出来计不对数。我当年刷这道题时也踩过这个坑所以今天把整道题的拆解过程、最优解推导、以及面试官大概率会追问的点一次讲清楚。不管你是刚开始刷题的校招同学还是准备跳槽的社招开发这篇都值得花十分钟认真看一遍。1. 题目拆解在“数三角形”之前先数清楚边界1.1 有效三角形的定义为什么用“任意两边之和大于第三边”给定一个数组 nums我们要统计有多少个下标三元组 (i,j,k) 能组成三角形。数学定义是“任意两边之和大于第三边”这是一个全称量词三条边里随便抽两条加起来都要大于剩下那条。严格大于等于也不行。如果数组是乱序的这三个条件缺一不可。比如 [4, 7, 2]你判断 4 2 7 不成立它就不能组成三角形但如果换成 [4, 6, 2]4 2 6等于也不行。只有像 [3, 4, 5] 这样任意两边之和都大于第三边才是有效三角形。而如果先把数组排好序假设 a b c那么问题会瞬间简化a c b 和 b c a 在边长都是正数时几乎自动成立。为什么说“几乎”因为只有负数会破坏这个结论在正整数/非负整数场景下c 本身最大c 加上另一个正数一定大于剩下的数。所以真正需要判断的就压缩成一个式子a b c。这个观察看起来简单却是后续所有解法的地基。面试时如果能把这个推理讲清楚比直接说“因为排序了所以只要判断和大于第三边”要显得扎实得多。1.2 输入的“非负整数”设定到底省掉了多少麻烦LeetCode 原题通常给的是非负整数很多解法直接声称“排序后检查 nums[i] nums[j] nums[k] 即可”。这个约束不是随意加的。三角形的边长必须是正数0 和负数不能作为边。我在模拟面试里习惯主动问一句输入能否保证是正整数如果面试官说“可能包含 0 或负数”我会在排序前先把非正数过滤掉。为什么因为在负数存在时排序后数组最左侧是负数负数加上一个正数也可能大于另一个数但这种组合在几何上没有任何意义更麻烦的是双指针的“单调性”证明依赖 a、b、c 都是正边长。过滤操作很简单nums [x for x in nums if x 0]如果过滤完数组长度不足 3直接返回 0。这么做会多一行代码但让你在边界条件上无懈可击。另外如果输入变成浮点数大于判断还要考虑精度算法题里一般不这么考但在工程里确实值得注意。边界理清楚之后我们先从最直白的暴力枚举开始。2. 暴力枚举面试中先写出来的那个版本2.1 三层循环的代码长什么样最直白的解法就是枚举所有下标三元组逐一判断是否能组成三角形。下面这份代码不依赖排序逻辑和数学定义完全一致def triangleNumber(nums): n len(nums) ans 0 for i in range(n - 2): for j in range(i 1, n - 1): for k in range(j 1, n): a, b, c nums[i], nums[j], nums[k] if a b c and a c b and b c a: ans 1 return ans因为下标 i j k所以同一组元素只会被枚举一次不会出现组合重复。这个版本最大的优点是“一定正确”。面试紧张时先写它能给你建立信心也让面试官看到你确实理解了题意。如果你把数组排序内层循环可以剪枝。排序之后 k 对应的数最大只需要判断 nums[i] nums[j] nums[k]一旦某个 k 不满足由于后面的数更大更不可能满足可以直接 breakdef triangleNumber(nums): nums.sort() n len(nums) ans 0 for i in range(n - 2): for j in range(i 1, n - 1): for k in range(j 1, n): if nums[i] nums[j] nums[k]: ans 1 else: break return ans注意 break 只跳出了最内层 k 循环外层 j 换一个值后新的 nums[j] 可能更大所以 k 要重新从 j 1 开始找。这个剪枝版在最坏情况下仍可能是 O(n^3)比如所有数都很小且无法触发 break 的场景但平均表现会好不少。2.2 暴力法真正的价值不是过题而是建立坐标系既然暴力解是 O(n^3)LeetCode 上限 n 一大就容易超时那为什么面试还要先讲它因为它的核心价值不是“过题”而是“确认题意”。在实际刷题中我还用暴力解干了一件更重要的事作为对数器。写完排序双指针的最优解后我会写一个随机小数组生成器生成几十组数据把暴力结果和双指针结果逐一对比。只要有一组不一致就说明双指针的边界写错了。这个方法成本极低却能在几分钟内帮你抓住 off-by-one 这类最隐蔽的问题。import random def brute(nums): # 上面第一个暴力版本 ... def two_pointer(nums): # 后面要讲的最优解 ... for _ in range(1000): nums [random.randint(0, 10) for _ in range(random.randint(0, 12))] assert brute(nums) two_pointer(nums)LeetCode 上提交失败一次要等好几秒本地对拍则是秒级反馈效率完全不一样。所以不要一上来就背双指针模板。先把暴力解写熟这会成为你之后所有优化版本的“参考答案”。面试时你甚至可以主动说“我先写一个暴力解确认边界再讲优化方案。”这种表现通常很加分。3. 排序 双指针正确解法的推导过程3.1 为什么排序是这道题的拐点暴力解已经帮我们确认了题意接下来要解决性能。关键问题是怎么把 O(n^3) 降到 O(n^2)排序是第一步。排序有两个直接收益第一三条边的大小关系被固定下来判断条件从三个缩成一个第二数组变成单调递增这为双指针的移动提供了理论依据。你可以这么想在乱序数组里双指针每次移动都很难判断该往哪边走因为你不知道下一个数是大是小一旦排好序左边小右边大移动方向就具有了明确语义。这个套路和“三数之和”很像先排序固定一个数再在剩余区间内用双指针扫描。区别在于三数之和要找精确相等这里要找“大于某个阈值”所以计数方式不同。很多人在面试时只背了模板却说不清为什么排序这是最大的扣分点。3.2 双指针移动规则一个负责保底一个负责计数具体怎么做我们先固定最长边也就是排序后的数组从右往左看。为什么固定最长边而不是最短边或中间边因为固定最长边后剩下两条边都小于等于它三角形条件只剩一个a b c。如果你固定最短边另外两条边之间的大小关系不确定还得额外判断双指针推不下去。伪代码思路如下排序。外层循环 i 从 n-1 往左走到 2把 nums[i] 当作最大边 c。内层在 [0, i-1] 范围内放两个指针left 0right i - 1。判断 nums[left] nums[right] c。成立说明 nums[left] 到 nums[right-1] 这一段里的任意一个数都可以和 nums[right]、nums[i] 组成三角形计数增加 right - left然后 right 左移。不成立说明 nums[left] 太小带不动当前最大的 right那就 left 右移。写成代码就是from typing import List def triangleNumber(nums: List[int]) - int: nums.sort() n len(nums) ans 0 for i in range(n - 1, 1, -1): left 0 right i - 1 c nums[i] while left right: if nums[left] nums[right] c: ans right - left right - 1 else: left 1 return ans我建议你拿 [2, 2, 3, 4] 手算一遍外层最大边 c4left0 指向2right2 指向3234count 2-02right1。此时 left0right1224 不成立left1。left1right1循环结束。这一轮 count2对应 [2,3,4] 和 [2,3,4]两个下标不同的2。外层 c3left0 指向2right1 指向2223count 1对应 [2,2,3]。总数 3。手动模拟完你就明白为什么它不是每次加 1而是加 right-left。3.3 正确性证明为什么 right - left 可以直接累加这是最容易被面试官追问的地方。很多人写成if nums[left] nums[right] c: ans 1 right - 1这么写只统计了一个组合把其余可行组合全漏了。关键在于当 nums[left] nums[right] c 成立时由于数组有序把 left 向右移到任意位置 xleft x rightnums[x] nums[left]所以 nums[x] nums[right] 一定也大于 c。也就是说对于当前固定的 right 和 c所有大于等于 nums[left] 的左端点都能组成三角形。这些左端点的个数就是 right - left。为什么不会和之前的轮次重复因为每一轮只处理了一个固定的最大边 c。任何一个三元组在排序后都有唯一的最大值如果最大值重复则对应多个下标组合但每一组都被包含在“最大边为 nums[i]”的那一轮中所以计数天然不重不漏。这就像把一个大任务按“最大值”切分成了多个互不相交的小任务。4. 边界条件与实测让代码从“能跑”变成“能过”4.1 三类必测用例重复值、零、极值长度写算法题代码能跑通样例只是开始。我强烈建议你在本地跑下面这张表覆盖最容易出错的几类情况输入数组期望结果说明[1, 1, 1]1等边三角形111 严格成立[1, 2, 3]0123相等不构成三角形[2, 2, 3, 4]3官方示例重复值场景[0, 0, 0]00 不能作为边长[5, 4, 3, 2]3乱序输入排序后为 [2,3,4,5][1, 2, 2, 2, 2]8重复值更多时的组合计数[] 或 [1] 或 [1, 2]0元素不足三个我重点说下 [1, 2, 2, 2, 2]。排序后第一个 1 可以和任意一个 2 以及另一个 2 组成 [1,2,2]这样的组合有 C(4,1) 4 个同时任意三个 2 也能组成 [2,2,2]组合数是 C(4,3) 4总数为 8。如果双指针版本的输出不是 8大概率是重复值处理出了问题。还有一组值得测的边界是“边长极度接近”比如 [1, 1, 1, 1, 1]任意三个 1 都能组成三角形结果应该是 C(5,3) 10。这类用例能检验你的代码是否会漏掉等边三角形。4.2 复杂度对比和复杂度陷阱这道题从暴力到最优复杂度变化很清晰解法时间复杂度空间复杂度备注暴力不排序O(n^3)O(1)一定正确只适合小数据排序剪枝暴力O(n^3) 最坏O(1)剪枝可加速平均情况排序双指针O(n^2)O(log n)排序栈标准最优解排序二分O(n^2 log n)O(log n)可作为过渡思路复杂度陷阱在于内层 while 循环很多人误以为自己写着写着就变成 O(n^2 log n) 或 O(n^3)其实双指针的 left 和 right 每次循环至少有一个移动内层最多 O(n)外层 O(n)总 O(n^2)。这个结论写代码前就要想清楚面试官很爱问“你为什么说它是 O(n^2)”。空间复杂度方面不算返回值排序如果用快排栈空间平均 O(log n)严格实现可能 O(n)。一般回答“排序需要的额外空间”就够了。如果你在面试时能主动补一句“这里是排序的空间不是缓存数组的空间”面试官会认为你很严谨。4.3 整数溢出的隐蔽风险LeetCode 原题的数值范围很小nums[left] nums[right] 几乎不可能溢出。但面试官特别喜欢扩展“如果 nums[i] 接近 int 上限怎么办”在 C 或 Java 里两个 int 相加可能溢出成负数导致判断错误。解决办法有两个用更大的类型long long 或 long。改成减法判断if (nums[left] c - nums[right])这样不会产生加法溢出。Python 没有整型溢出但理解这个风险依然重要因为这体现的是工程思维。另外如果输入可能包含 0 或负数最稳妥的做法是排序前过滤nums [x for x in nums if x 0] if len(nums) 3: return 0 nums.sort()过滤之后再做双指针整个证明过程就不用为“负数会不会影响单调性”额外解释了。这个代码习惯在面试里非常实用也可以顺带展示你想问题比题目本身更全面。5. 面试官常见的追问方向从会做一道题到会一类题5.1 改成输出所有可行三元组如果面试官把题目改成“不仅要个数还要输出所有可行三元组”计数型双指针就不够用了。原因很直接可行三元组的数量最坏情况下是 O(n^3)比如数组全是 10任意三个都能组成三角形输出规模本身就是 O(n^3)所以任何算法都无法低于这个复杂度。这时候可以退回到排序后的枚举法一边枚举一边收集答案。你能说出这一点面试官会认为你对“算法下界”有概念而不是只会背模板。计数问题和构造/输出问题的难度常常是不同的双指针能批量计数正是因为它不需要展开每一组具体答案。如果你在简历里写过“对算法复杂度有理解”这就是一个很好的体现机会。5.2 二分答案与双指针的取舍除了双指针还有一种思路也很常用固定最小两条边用二分查找第三边。排序后对于固定的 i、j所有满足 nums[k] nums[i] nums[j] 的 k 都可行而且这些 k 构成一个连续区间。from bisect import bisect_left from typing import List def triangleNumber(nums: List[int]) - int: nums.sort() n len(nums) ans 0 for i in range(n - 2): for j in range(i 1, n - 1): k bisect_left(nums, nums[i] nums[j], j 1) ans k - j - 1 return ansbisect_left 返回第一个大于等于 nums[i]nums[j] 的位置这个位置之前、j 之后的元素都满足和小于两边之和的条件。这段代码比双指针好理解但多了一个 log n。面试时可以先讲二分再讲双指针优化最后让面试官看到你能自己把 log n 去掉这会是很加分的叙事线。5.3 和其他数组双指针题目的联系“有效三角形的个数”不是孤立题。它和“三数之和”“最接近的三数之和”“接雨水”共享同一种思维工具排序后用双指针维护一个单调区间。区别只在于判断条件和累加方式。三数之和排序后固定一个数双指针找两个数等于 target要去重。最接近的三数之和双指针根据当前和与 target 的差决定移动方向。有效三角形个数固定最大边后双指针统计所有满足两边之和大于最大边的组合累加区间长度。如果你能把这几道题放在一起复习相当于掌握了一类题型而不是一道题。面试官随机换一个类似题你也能很快想到“排序 双指针”这个框架。我自己在准备面试时会把这类题统一归类到“有序数组上的区间计数”复盘效率高很多。6. 写在代码之外我实际刷这道题的几个体会6.1 一个排序习惯救了我很多次我最初刷这道题时直接看了题解然后背诵代码结果过了两周再写还是把 ans right - left 写错。后来我改成“先手推样例再写代码”的习惯效果好了很多。具体做法是拿到一道题先不急着开 IDE拿笔在纸上把样例跑一遍。对这道题你就跑 [2,2,3,4]把 left、right、i 每一步的变化都写出来。整个过程大概三分钟但它会帮你把“为什么加 right-left”变成一种肌肉记忆而不是死记结论。这个习惯后来帮我解决了很多双指针类的题目包括三数之和和接雨水。6.2 复盘时要能回答三个问题我觉得一道题真正刷完的标志不是提交通过而是能回答清楚下面三个问题为什么排序后只需要判断 a b c为什么外层固定最长边而不是最短边为什么 nums[left] nums[right] c 时答案加的是 right - left如果你能不看代码把这三个问题讲明白那这道题在面试基本稳了。反过来如果你只记得模板面试官深挖两句就会露馅。6.3 最后再说一个面试节奏的小技巧面试时你可以先写暴力解确认题意然后主动说“我知道这里有排序加双指针的 O(n^2) 解法我再优化一下。”很多面试官对候选人最大的要求不是一次性写对最优解而是思路清晰、有调试意识。这道“有效三角形的个数”恰恰是展示这两种素质的好题目。我在实际面试中见过不少人因为急着直接写双指针结果边界条件写错又不敢回退到暴力解最后整道题卡死。先暴力、再优化的节奏反而显得更稳。