企业官网建设流程全解析

面试里有一类题特别有意思：题面看起来像小学数学，实际做起来却能把排序、双指针、边界处理全考一遍。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 不满足，由于后面的数更大，更不可能满足，可以直接 break：

def 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。如果你固定最短边，另外两条边之间的大小关系不确定，还得额外判断，双指针推不下去。

伪代码思路如下：

1. 排序。
2. 外层循环 i 从 n-1 往左走到 2，把 nums[i] 当作最大边 c。
3. 内层在 [0, i-1] 范围内放两个指针：left = 0，right = i - 1。
4. 判断 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] 手算一遍：

• 外层最大边 c=4，left=0 指向2，right=2 指向3，2+3>4，count += 2-0=2，right=1。
• 此时 left=0，right=1，2+2>4 不成立，left=1。
• left=1，right=1，循环结束。这一轮 count=2，对应 [2,3,4] 和 [2,3,4]（两个下标不同的2）。
• 外层 c=3，left=0 指向2，right=1 指向2，2+2>3，count += 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 向右移到任意位置 x（left <= x < right），nums[x] >= nums[left]，所以 nums[x] + nums[right] 一定也大于 c。也就是说，对于当前固定的 right 和 c，所有大于等于 nums[left] 的左端点都能组成三角形。这些左端点的个数就是 right - left。

为什么不会和之前的轮次重复？因为每一轮只处理了一个固定的最大边 c。任何一个三元组，在排序后都有唯一的最大值（如果最大值重复，则对应多个下标组合，但每一组都被包含在“最大边为 nums[i]”的那一轮中），所以计数天然不重不漏。这就像把一个大任务按“最大值”切分成了多个互不相交的小任务。

4. 边界条件与实测：让代码从“能跑”变成“能过”

4.1 三类必测用例：重复值、零、极值长度

写算法题，代码能跑通样例只是开始。我强烈建议你在本地跑下面这张表，覆盖最容易出错的几类情况：

我重点说下 [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 复杂度对比和复杂度陷阱

这道题从暴力到最优，复杂度变化很清晰：

复杂度陷阱在于内层 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 ans

bisect_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) 解法，我再优化一下。”很多面试官对候选人最大的要求不是一次性写对最优解，而是思路清晰、有调试意识。这道“有效三角形的个数”恰恰是展示这两种素质的好题目。我在实际面试中见过不少人因为急着直接写双指针，结果边界条件写错又不敢回退到暴力解，最后整道题卡死。先暴力、再优化的节奏，反而显得更稳。