企业官网建设流程全解析

“有效三角形的个数”是力扣上一道很有代表性的数组题，编号611。乍一看就是“给一堆数字，数一数能组成多少个三角形”，但真正上手之后你会发现，这道题考的根本不是怎么判断三角形，而是怎么把三层循环降到两层。我当时第一次做的时候老老实实写了三重循环，结果本地跑起来都要卡好一会儿，更别说在在线评测平台上了。这道题非常适合正在刷题、想巩固排序和双指针套路的人拿来反复琢磨，把复杂度分析、指针移动逻辑、边界条件这些基本功一次性串起来。

1. 先从暴力解说起：为什么三层循环必挂

1.1 题目到底要我们算什么

先弄清楚题意。输入是一个非负整数数组，要求统计其中能组成三角形的三元组个数。这里的“三元组”指的是三个不同下标，但值可以重复。比如数组[2, 2, 3, 4]里有两个 2，它们分别参与组合时要算作两个不同三元组，所以代码里不能去重，去重反而会漏答案。

三角形的判定规则是“任意两边之和大于第三边”，这里要注意等号不满足，2 + 3 = 5和5不能组成三角形。另外数组里可能出现 0，0 作为边长肯定没法进入合法三角形，但不用特判，排序后的判断条件会自然把它排除掉。

这些细节看起来小，但对答案影响很大。很多人在第一步就容易跑偏，比如想着“先排序再去重”，结果题目要求统计下标组合，去重之后合法数量直接变少，样例可能还看不出来，一提交就知道错了。判断条件里为什么排序后可以简化，后面单独说，这里先把题意理解透。

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 >= b；
• b + 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 与 C++

4.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 ans

C++ 版：

class Solution { public: int triangleNumber(vector<int>& 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 = 3，left = 0，right = 2。此时nums[0] + nums[2] = 2 + 3 = 5 > 4，成立。根据上面的性质，left = 0 和 left = 1 两个 2 都能和 3、4 组成三角形，所以 ans 加 2。然后 right 左移变成 1。

接着 left = 0，right = 1，nums[0] + nums[1] = 2 + 2 = 4不大于 4，不成立，left 右移变成 1。此时 left == right，最长边为 4 的统计结束。

再把最长边定为 3，也就是 i = 2，left = 0，right = 1。nums[0] + nums[1] = 4 > 3，成立，ans 加 1，然后 right 左移变成 0，循环结束。

最后 ans = 3。手动枚举验证一下：可以组成三角形的是(2a, 2b, 3)、(2a, 3, 4)、(2b, 3, 4)，正好 3 个。

用表格展示整个过程会更清楚：

4.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] == target，nums[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 同套路变体题清单

这道题的套路可以平移到不少题目上，我列个简单的对照表：

其中“三角形的最大周长”最典型：排序后从后往前遍历，找到第一个满足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；再后来把二分版本也写了一遍，对“单调性”这三个字的理解加深了不少。

如果你刚开始刷题，不建议只看题解就完事。看完思路后，合上代码自己写一遍，再拿小例子手动走一遍，最后跑一跑随机对拍。整个过程下来，排序、双指针、复杂度分析、边界处理这些基本功都会得到实打实的锻炼。以后再遇到“统计满足某条件的三元组个数”这类题，第一反应就会是排序 + 固定一个点 + 双指针，这条肌肉记忆就是靠这道题建立起来的。