优化到O(n²))
1. 题目拆解为什么暴力解法是最容易掉进去的坑1.1 题面描述与三角形的关键条件力扣611题“有效三角形的个数”题面很简洁给定一个包含非负整数的数组nums返回其中可以组成三角形三条边的三元组个数。所谓“可以组成三角形”就是三条边满足任意两边之和大于第三边不能取等号——三条边2, 3, 5时因为2 3 5构不成三角形。我第一次刷这题时第一反应就是三层循环枚举所有下标组合对每一组判断一下。这种思路不能说错因为它确实能算出答案但问题在于复杂度。数组长度n一旦上到几百上千三重循环就会跑得非常痛苦。力扣上这题的数据范围我记得是1 nums.length 1000如果你无脑三层循环最坏情况要枚举约C(1000, 3)种组合算下来大概 1.66 亿组每组还要做三次不等式判断。Python 直接超时C 勉强能压线但也不优雅。还有个常见误区很多人会先排序然后“如果最小两边之和小于等于第三边就提前 break减少无效判断”。这种剪枝确实能挡掉一部分数据但最坏情况依然存在。比如数组是1, 2, 3, 4, 5, ..., 2000几乎每个三元组都满足三角形条件剪枝根本剪不掉多少整体依然是O(n^3)。所以这道题真正考察的不是你知不知道三角形判定条件而是你能不能把三重循环优化成两重甚至更低。1.2 暴力枚举的复杂度账要算清楚我把暴力代码写出来方便对照后面优化def triangle_number_bruteforce(nums): n len(nums) ans 0 for i in range(n): for j in range(i 1, n): 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这代码逻辑完全正确但n 1000时内层循环次数约为 1.66 亿次每次要取三个数、做三次加法、三次比较。Python 大约需要几十秒明显不可接受。哪怕用 C当n 5000时也要跑好几秒。核心问题在于我们没有利用数组内部的任何结构。如果先把数组排好序三角形的三个判断条件就能大幅简化这是整道题最重要的突破口。2. 排序的意义把“三个条件”压缩成“一个条件”2.1 不等式组的数学化简假设我们把一个三元组从小到大排好序得到a b c。那么三角形的三个条件a c b因为c b且a是非负数所以a c c b。但注意这里需要严格大于如果a 0且c b那么a c b不满足。这种情况后文单独讨论先把框架搭起来。b c a同理b c远大于a一般没问题。a b c这条不保证成立比如2, 3, 6就不满足2 3 6。所以排序后只要a b c成立再加上a 0这个前提三个条件就全部满足。本质上判断条件从“三选三”降维成了“只看最小两边之和是否大于最大边”。这一步看起来不起眼但它让后续的双指针扫描成为了可能。为什么一定要排序因为只有让数组有序我们才能用指针收缩的方式快速跳过大量无效组合。如果不排序每个三元组都得独立判断信息完全无法复用。2.2 固定最大边从大到小枚举的直觉有了上面的化简我们自然想到枚举数组中的每个位置作为最大边c然后在它左边找所有满足a b c的二元组(a, b)。枚举顺序从大到小比较舒服因为最大边确定后剩余区间是[0, i-1]我们只关心这个区间内部有多少对组合满足条件。如果从小到大枚举后面还要处理更大边的覆盖问题不如从大到小直观。举个例子数组排序后为[2, 2, 3, 4]我们从后往前看固定最大边4左侧区间[2, 2, 3]中2 3 4成立两个2都能和3组合成三角形所以有 2 组。固定最大边3左侧区间[2, 2]中2 2 3成立有 1 组。答案总共 3 组。这个手算过程其实就是双指针的雏形在左侧区间内我们要高效统计“有多少对之和大于某个固定值”。如果左侧区间也是乱序的那还是得暴力。但因为整个数组已经有序我们就可以用两个指针从两端向中间逼近一次跳过一大批组合。3. 双指针统计O(n²)解法的推导与实现3.1 指针收缩的数学依据固定最大边nums[i]后设左指针left指向区间[0, i-1]的最小值右指针right指向区间最大值。现在分两种情况第一种情况nums[left] nums[right] nums[i]由于数组递增nums[left]是当前区间内最小的数。那么对于任意位置x只要left x right都有nums[x] nums[left]所以nums[x] nums[right] nums[left] nums[right] nums[i]也就是说以nums[right]作为次长边左边从left到right-1的任何数作为最短边都能和nums[i]组成三角形。这一下就能累加right - left个组合不需要再一个数一个数试。之后right左移一位因为以当前nums[right]为次长边的所有组合已经全部统计完了。第二种情况nums[left] nums[right] nums[i]这说明当前的nums[left]太小了。即使和区间内最大的nums[right]搭配都无法满足三角形条件那它和其他任何更小的数搭配就更不可能了。所以left右移一位放弃这个最小值。这种收缩逻辑和“两数之和”“盛最多水的容器”非常像。关键在于识别出什么时候可以批量计数什么时候只能移动指针。批量计数的底气来自排序后的单调性。3.2 代码实现与细节说明看代码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每一步都对应前面说的情况i枚举的是最大边下标从n-1一直走到2保证左边至少有两个数可供选择。left初始指向 0right初始指向i-1也就是最大边左侧区间的两端。满足条件时ans right - left然后right - 1不满足时left 1。用前面[2, 2, 3, 4]的例子手动跑一遍排序后数组不变。i 3最大边为 4left 0right 2。nums[0] nums[2] 5 4所以ans 2 - 0 2right 1。此时left 0 1nums[0] nums[1] 4 4不成立等于不行left 1循环结束。接着i 2最大边为 3left 0right 1nums[0] nums[1] 4 3ans 1 - 0 1right 0循环结束。总共ans 3正确。3.3 另一种思路二分查找方案对比除了双指针还有一种常见写法是枚举两条短边然后在剩余区间二分查找满足条件的最长边位置。思路是固定i, j两条较短边在[j1, n-1]区间找最大的k使得nums[j] nums[k] nums[i]。因为区间有序可以直接用二分。复杂度是O(n^2 log n)。我整理了一张对比表方便大家根据实际场景选择方案时间复杂度空间复杂度优点缺点暴力三重循环O(n^3)O(1)思路最简单数据一大就超时固定短边二分O(n^2 log n)O(log n)思路直观容易扩展比双指针多一个log固定最大边双指针O(n^2)O(log n)最优代码最简洁需要理解批量计数原理在原题n 1000的限制下双指针和二分都能过但双指针代码量更少也更能体现对单调性的理解。面试时如果能把“为什么ans right - left不会漏”讲清楚会比单纯背模板加分不少。4. 边界条件与实战避坑4.1 长度不足、零元素与重复值先看几个容易出错的点。数组长度不足 3直接返回 0这个大多数人都知道但别写在循环里让它自然越界。加一行提前判断既安全又清晰。零元素题目说的是非负整数所以0会出现。0 不能作为三角形边因为0 任意数都不可能严格大于第三边除非第三边也是负数但这里没有负数。好在双指针代码天然能处理如果nums[left] 00 nums[right] nums[i]通常不成立left会不断右移0 自然被排除不需要额外过滤。不过要特别注意如果排序后最大边也是 0比如数组全是 0那么i从n-1开始枚举的每一步里nums[left] nums[right] 0 0都不成立最终答案也是 0不会误判。重复元素[2, 2, 3, 4]已经展示了两个 2 是不同下标会被分别统计。原因在于双指针处理的是“下标组合”而不是“值组合”每个下标位置天然独立。这是很多人疑惑的地方实测跑一遍就明白不用做任何去重操作。4.2 整数溢出与“加法改减法”技巧在力扣原题中nums[i]上限不算高int相加不会溢出。但如果这题出现在其他 OJ或者数据范围被放大到1e9级别nums[left] nums[right]就可能溢出。稳妥的做法是把判断条件改写为if nums[right] nums[i] - nums[left]: ans right - left right - 1 else: left 1为什么可以这样改因为nums[i] nums[left]数组有序所以nums[i] - nums[left]是非负数不会溢出。判断逻辑完全等价于原来的nums[left] nums[right] nums[i]只是避开了两数相加的溢出风险。这种小技巧在写 C 或 Java 时特别实用推荐记一下。4.3 常见错误清单我整理了自己刷题时踩过的一些坑列出来给各位参考错误类型错误写法/表现后果忘排序直接套双指针指针移动无单调性答案完全错误循环范围写错for i in range(n - 1, 1, 1)循环根本不执行答案恒为 0累加写错ans 1而不是ans right - left大量组合被漏掉等于判定错误用而不是把退化三角形也算进去了左右指针更新颠倒满足条件时left逻辑反转统计结果全乱这里重点说说“等于判定”这个坑。2, 3, 5三条边时2 3 5这是退化情况不能算三角形。题目要求的是严格大于所以比较运算符必须写成。我第一次写的时候顺手写成了结果[2, 2, 4]这种数据被错误地算成一组必须特别注意。5. 从本题延伸双指针题型的识别与刷题心法5.1 什么时候该想到双指针刷多了就会发现双指针不是灵光一现而是有明显特征可循。我总结出三个信号题目要求统计或寻找组合暴力解法通常是两重或三重循环。数组可以排序排序不会破坏问题的本质。排序后指针移动方向能带来单调性收益——也就是某个条件一旦成立就能跳过一片组合。最典型的三件套就是“两数之和”“三数之和”“盛最多水的容器”。另一道经典题“三数之和”要求找三个数和为 0思路同样是先排序然后固定一个数剩余区间用双指针扫描。你会发现这两题的代码骨架几乎一模一样只是判断条件和累加逻辑不同。5.2 通用套路排序、固定基准、双指针扫描拿这题总结一下可复用的流程第一步排序。让数组变得有序这是后续所有优化的前提。第二步确定基准。根据题意决定固定最大边、最小边还是目标值。本题固定最大边最自然因为三角形条件的化简结果直接指向“较小两边之和大于最大边”。第三步双指针扫描剩余区间。根据当前两个指针之和与目标的关系决定是做一次批量计数还是移动某一个指针。第四步验证边界。长度不足、0 元素、溢出、严格大于还是大于等于这些细节决定代码能不能过边界用例。如果想进一步拓宽这道题还有几个变体值得思考如果要求输出所有三元组而不是只计数怎么写去重逻辑如果数组长度变成1e5O(n^2)也过不了有没有更高效的解法第二个问题至今没有简单答案说明这类题目的复杂度瓶颈就在排序后的两两枚举上能在面试中把复杂度分析讲透就已经比大多数人强了。刷题这件事最怕的就是背模板。我当初把双指针模板背得滚瓜烂熟遇到“有效三角形的个数”还是卡了半天因为模板里没教过“批量计数”这种操作。后来我把每个指针移动背后的数学依据都推导了一遍才真正理解为什么ans right - left是安全的。建议大家刷这题时不要只看答案而是把“固定最大边”和“为什么一次能加那么多个组合”这两点亲手推一遍推通了双指针这类题目才算是真正入门了。
