“有效三角形的个数”是力扣上一道很有代表性的数组题编号611。乍一看就是“给一堆数字数一数能组成多少个三角形”但真正上手之后你会发现这道题考的根本不是怎么判断三角形而是怎么把三层循环降到两层。我当时第一次做的时候老老实实写了三重循环结果本地跑起来都要卡好一会儿更别说在在线评测平台上了。这道题非常适合正在刷题、想巩固排序和双指针套路的人拿来反复琢磨把复杂度分析、指针移动逻辑、边界条件这些基本功一次性串起来。1. 先从暴力解说起为什么三层循环必挂1.1 题目到底要我们算什么先弄清楚题意。输入是一个非负整数数组要求统计其中能组成三角形的三元组个数。这里的“三元组”指的是三个不同下标但值可以重复。比如数组[2, 2, 3, 4]里有两个 2它们分别参与组合时要算作两个不同三元组所以代码里不能去重去重反而会漏答案。三角形的判定规则是“任意两边之和大于第三边”这里要注意等号不满足2 3 5和5不能组成三角形。另外数组里可能出现 00 作为边长肯定没法进入合法三角形但不用特判排序后的判断条件会自然把它排除掉。这些细节看起来小但对答案影响很大。很多人在第一步就容易跑偏比如想着“先排序再去重”结果题目要求统计下标组合去重之后合法数量直接变少样例可能还看不出来一提交就知道错了。判断条件里为什么排序后可以简化后面单独说这里先把题意理解透。1.2 暴力枚举的正确写法与复杂度如果只看题目描述最朴素的做法就是三层循环直接枚举所有下标组合代码如下from typing import List class Solution: def triangleNumber(self, nums: List[int]) - int: n len(nums) ans 0 for i in range(n): for j in range(i 1, n): for k in range(j 1, n): if nums[i] nums[j] nums[k] and nums[i] nums[k] nums[j] and nums[j] nums[k] nums[i]: ans 1 return ans注意因为原数组不一定有序三个不等式一个都不能少。这个版本逻辑上完全正确问题出在性能上。时间复杂度是组合数 C(n, 3)。当 n 1000 时组合数大约是 1.67 亿次循环就算每次循环只做常数时间操作在常见的在线评测平台上也是必挂的。Python 跑这种规模基本要几十秒C 也得几秒。有人会说那我先排序排序后只需要判断一次nums[i] nums[j] nums[k]不就行了吗确实可以简化判断但循环层数没变依然是组合数级别的枚举照样超时。所以暴力解法只能用来做小数据校验或者作为理解题意的起点。真正能 AC 的解法必须想办法把枚举量降下来。2. 排序让判断条件从三个变成一个2.1 排序后为什么只需检查一个不等式三角形判定原本要检查三个不等式a b c、a c b、b c a。在数组无序时这三条一个都不能少因为你不知道哪条边最大。但排序之后情况完全不同。假设排序后三条边从小到大依次是a b c此时只需要检查a b c。为什么因为如果a b c成立那么a c b必然成立a c a b c bb c a也必然成立b c c a这里用到的是a 0的前提。所以核心条件只剩一个最小两边之和大于最长边。这一下子让后续的统计变得清爽得多。这个简化是整个双指针解法的基石。如果不排序就去谈双指针根本无从下手因为数组元素的数值顺序是乱的你没法通过指针位置的移动来推断数值大小的变化。排序给了一个稳定的“单调性”后面所有优化都建立在这个单调性之上。2.2 排序不会改变答案有人可能会犹豫排序改变了数组顺序会不会影响三元组的计数不会。三角形判断只关心数值大小不关心下标顺序。我们排成升序只是方便从数值关系上做推断。原本合法的三元组排序后依然合法原本不合法的排序后也依然不合法因为三边之间的数值关系没有因为排序而改变。排序的代价是 O(n log n)对 n 1000 来说微不足道。收益是巨大的它把“三条件判断”变成“单条件判断”并且给后续双指针提供了关键的单调性。从复杂度角度看这一步是典型的“用小代价换大优化”也是面试时非常值得拿出来讲透的一个点。3. 双指针核心固定长边一次跳一片3.1 为什么要固定最长边排序之后问题变成了对每个可能的最长边 c统计它左边有多少对(a, b)满足a b c并且 a、b、c 来自不同下标。那为什么固定最长边而不是固定最短边你可以试着固定最短边然后用双指针去找两条较长边但此时条件会变成“两条较长边中较短的那条 最短边 最长边”指针移动时分类讨论非常麻烦统计时还要处理更多位置关系。固定最长边则把问题转化成一个非常清爽的、类似两数之和的模型在一段有序数组中找有多少对元素的和大于某个目标值。所以思路的出发点就是让最大边做锚点在它左边用双指针找配对。3.2 关键性质“一次跳一片”是怎么来的这是整个算法的灵魂也是很多题解没有讲透的地方。设最长边下标为 i双指针分别为 left 和 right其中left right i。当nums[left] nums[right] nums[i]成立时我们不需要只给答案加 1而是可以直接加上right - left。原因很简单数组是升序的对于任意下标 p只要left p right - 1都有nums[p] nums[left]于是nums[p] nums[right] nums[left] nums[right] nums[i]这意味着从 left 到 right - 1 这right - left个元素每一个都能和nums[right]、nums[i]组成合法三角形。所以一次性计完这一整段。注意这里不包含 right 本身。因为 left 和 right 必须是两个不同位置当前 right 是作为“较长的短边”参与组合的。如果写成right - left 1就会把nums[right]和它自己配对既违反了下标约束也会重复统计。这个“一段一段跳”的特性正是双指针能把 O(n³) 降到 O(n²) 的根本原因。每次不是只找到一个合法组合而是找到一整段合法组合。3.3 指针移动逻辑与不重不漏的保证那指针到底怎么移动当nums[left] nums[right] nums[i]成立时说明当前nums[right]作为“第二长边”的所有合法组合已经统计完所以 right 向左移动一位去尝试更小的第二长边。当条件不成立时说明当前nums[left]太小就算配上区间里当前最大的nums[right]也无法大于nums[i]那 left 只能向右移动把最小的候选值增大。整个流程等到 left right 时结束表示区间内已经没有可配对的两根指针。为什么这样不重不漏因为每个合法三元组都可以按“最长边下标 i、第二长边下标 right”唯一归类。固定 i 之后某个 right 在循环过程中只会被处理到一次而 left 取遍所有能让不等式成立的左侧位置所以每个三元组恰好只会被计数一次。这也是面试时如果被追问“会不会重复”时需要能讲清楚的逻辑。4. 可直接提交的实现Python 与 C4.1 Python 版与 C 版好了直接上能提交的代码。Python 版from typing import List class Solution: def triangleNumber(self, nums: List[int]) - int: nums.sort() n len(nums) ans 0 for i in range(n - 1, 1, -1): left, right 0, i - 1 while left right: if nums[left] nums[right] nums[i]: ans right - left right - 1 else: left 1 return ansC 版class Solution { public: int triangleNumber(vectorint nums) { sort(nums.begin(), nums.end()); int n nums.size(); int ans 0; for (int i n - 1; i 2; --i) { int left 0, right i - 1; while (left right) { if (nums[left] nums[right] nums[i]) { ans right - left; --right; } else { left; } } } return ans; } };两个版本逻辑完全一样。有几个细节值得注意i 从n - 1往左走到 2而不是走到 0 或 1因为每个最长边前面至少要留两个元素否则 left 和 right 凑不成一对Python 里range(n - 1, 1, -1)是左闭右开所以最后取到的 i 是 2正好满足条件C 的sort是对整个数组升序排序排序后数组顺序变了但前面已经论证过这不影响答案。4.2 手把手模拟一个例子拿[2, 2, 3, 4]来完整跑一遍。排序后数组不变还是[2, 2, 3, 4]。先把最长边定为 4也就是 i 3left 0right 2。此时nums[0] nums[2] 2 3 5 4成立。根据上面的性质left 0 和 left 1 两个 2 都能和 3、4 组成三角形所以 ans 加 2。然后 right 左移变成 1。接着 left 0right 1nums[0] nums[1] 2 2 4不大于 4不成立left 右移变成 1。此时 left right最长边为 4 的统计结束。再把最长边定为 3也就是 i 2left 0right 1。nums[0] nums[1] 4 3成立ans 加 1然后 right 左移变成 0循环结束。最后 ans 3。手动枚举验证一下可以组成三角形的是(2a, 2b, 3)、(2a, 3, 4)、(2b, 3, 4)正好 3 个。用表格展示整个过程会更清楚inums[i]leftrightnums[left] nums[right]比较结果ans34022 3 55 4 成立234012 2 44 4 不成立23411-循环结束223012 2 44 3 成立32310-循环结束34.3 细节坑计数、边界与重复元素我最早写这道题的时候第一个版本就把ans right - left写成了ans right - left 1结果样例直接算错。原因就是前面说的right 这个位置已经被当成“第二长边”了不能再把自己也当成 left 算进去。另一个容易踩的坑是忘记排序。不排序直接跑双指针结果一定是错的因为指针移动依赖数组整体有序性。还有下标边界。如果 i 的循环范围写错比如让 i 走到了 0 或 1内层 left 和 right 连一对都凑不出来虽然不一定报错但逻辑上是错的。最好一开始就在纸上确认最长边前面必须至少有两个元素。重复元素也不需要做任何特殊处理。题目统计的是不同下标组合值相同但下标不同就算不同三元组。用 set 去重会改变问题语义答案会变小。最后提一个数据范围的细节本题nums[i]最大值不超过 1000所以nums[left] nums[right]不会溢出 int。但如果题目换成更大的数值范围C 里最好把加法运算转成long long避免溢出导致判断出错。5. 复杂度分析与二分进阶5.1 为什么总复杂度是 O(n²)先分析双指针解法的时间复杂度。排序是 O(n log n)。主循环中i 从大到小遍历所有可能的最长边共n - 2次。对每个 i内层 left 和 right 从两端向中间移动left 只会增加right 只会减少所以每个 i 内层循环最多移动 O(i) 次。总的移动次数是O(n) O(n-1) ... O(2) O(n²)所以总体复杂度是 O(n log n n²)也就是 O(n²)。空间复杂度是 O(1)不计排序递归栈的话。这个复杂度对本题很合适。n 1000 时n² 10^6 级别在在线评测平台上毫秒级完成和暴力解法的 1.67 亿次循环完全不是一个量级。5.2 二分查找解法换一种统计方式如果你想把“统计合法区间”的思路练熟还可以写一个二分查找版本。固定最长边下标 i 和次长边下标 j第三条边 k 必须满足nums[k] nums[j] nums[i]且k j。由于数组升序这个条件等价于找nums[k] nums[i] - nums[j]的第一个位置记作 pos那么从 pos 到 j - 1 的所有 k 都合法计入j - pos。代码如下from typing import List import bisect class Solution: def triangleNumber(self, nums: List[int]) - int: nums.sort() n len(nums) ans 0 for i in range(2, n): for j in range(1, i): target nums[i] - nums[j] pos bisect.bisect_right(nums, target, 0, j) ans j - pos return ans这里用bisect_right而不是bisect_left因为我们要找的是“第一个大于 target”的位置。如果nums[k] targetnums[k] nums[j] nums[i]是不满足三角形条件的所以必须严格大于。这个解法的时间复杂度是 O(n² log n)比双指针慢一些但代码思路更加直白也更容易证明正确性。两种方法都不错我个人建议都写一遍能加深对“排序 二分”和“排序 双指针”两种套路各自适用场景的理解。5.3 两种解法的适用场景对比从复杂度看双指针优于二分。但在实际面试中二分版本也不是没有价值。如果面试官问“能不能换个思路”你能从双指针切换到二分说明你对数组上的单调性理解得比较透。两种方法共同的前提都是“排序后数组具有单调性”区别只在于如何利用这个单调性双指针一次移动维护 left 和 right直接统计一整段合法区间二分逐对枚举 i 和 j用二分精确定位合法区间的起点。在 n 比较小、要求代码简洁时双指针是首选。在想要降低编码复杂度、或者面试官希望看到多思路对比时二分也是一个能说得通的方案。实际刷题中我更推荐先掌握双指针因为它的常数更小而且能顺带复习“夹逼”这个高频技巧。6. 面试怎么答题怎么变6.1 一条清晰的面试回答路径这道题如果出现在面试里推荐按下面这条路径讲先讲暴力解枚举所有三元组检查三个不等式O(n³)并明确说明 n 1000 时不可接受。再讲排序的动机排序后只需判断一个不等式而且为后续优化打下基础。然后讲双指针固定最长边用 left 和 right 在左侧夹逼计数每次当不等式成立时一次计入right - left个合法组合。最后主动提复杂度排序 O(n log n)主循环 O(n²)整体 O(n²)空间 O(1)。讲的时候最好手写一个例子比如[2,2,3,4]现场演示 ans 是怎么从 0 累加到 3 的。这样面试官能直观看到双指针“一次跳一片”的效果而不只是听你念结论。6.2 同套路变体题清单这道题的套路可以平移到不少题目上我列个简单的对照表题目核心思路复杂度有效三角形的个数排序 固定最长边 双指针计数O(n²)三角形的最大周长排序 从大到小找第一个可行三元组O(n log n)三数之和排序 固定一个数 双指针找两数O(n²)最接近的三数之和排序 固定一个数 双指针逼近目标O(n²)其中“三角形的最大周长”最典型排序后从后往前遍历找到第一个满足nums[i] nums[j] nums[k]的三个下标直接返回三数之和即可。因为排序后最长的、且尽量大的三边组合就在后面找到第一个合法的就是最大周长。6.3 有序场景与大数据场景的追问面试官还可能追加几个问题。如果数组本身已经有序呢那就省掉排序步骤双指针直接跑代码逻辑不用改。如果数组长度从 1000 变成 100000 呢O(n²) 就有点吃力了。这种追问一般不是为了让你现场写更高级的算法而是考察你是否清楚自己方案的适用边界。你可以回答如果数据范围变大可以考虑基于值域的计数 前缀和优化但这类做法通常要求数值范围不大而且实现复杂度高不是本题的常规考点。这样回答既诚实又显得对复杂度有敏感度。如果数值范围里有大整数呢要注意加法溢出C 里把nums[left] nums[right]的加法用long long承接。虽然这道题用不到但写出这个意识会让面试官更放心。7. 实测记录与个人踩坑7.1 我写错的那个计数公式文章前面提到了我第一次提交时把ans right - left写成了ans right - left 1样例[2,2,3,4]直接算出 5 而不是 3。排查方法其实很简单在循环里把left、right、nums[left]、nums[right]全打印出来看每一次计数到底加了什么马上就发现问题了。这种错误不丢人但能暴露出一个思维盲点写代码时有没有真正理解“right 自己不能当 left”这个约束。建议你也养成一个习惯写完计数类逻辑后先拿一个长度为 4 或 5 的小数组手动走一遍确认计数过程没有把同一个下标用两次。7.2 验证算法正确性的土办法想验证自己的实现是否正确有一个很实用的土办法写一个随机数组生成器生成长度 5 到 15 的小数组分别用暴力解法和双指针解法跑对比结果。随机测几百组如果全部一致正确性基本可以放心。这个小技巧在刷任何计数类题目时都特别好用。暴力解法虽然慢但正确性容易保证双指针解法效率高但逻辑复杂容易出边界错误。两者对拍能快速定位问题比自己盯着代码干瞪眼高效得多。7.3 个人练题体会这道题我刷过不止一遍每次都有点新感受。最初是单纯为了过题记住了“固定长边 双指针 ans right - left”后来再刷开始思考为什么不能固定短边为什么一次要加 right - left 而不是加 1再后来把二分版本也写了一遍对“单调性”这三个字的理解加深了不少。如果你刚开始刷题不建议只看题解就完事。看完思路后合上代码自己写一遍再拿小例子手动走一遍最后跑一跑随机对拍。整个过程下来排序、双指针、复杂度分析、边界处理这些基本功都会得到实打实的锻炼。以后再遇到“统计满足某条件的三元组个数”这类题第一反应就会是排序 固定一个点 双指针这条肌肉记忆就是靠这道题建立起来的。