做算法题的时候有一种快乐是题目本身只有一行描述但背后藏着一整类优化思路。有效三角形个数就是这样——表面上是几何问题实际上是排序和双指针的经典练兵场也是我算法题解系列第五篇想重点讲透的题目。题目很直白给你一个包含若干正整数的数组统计其中有多少个三元组三个不同下标可以组成三角形。很多初学者第一反应是三层循环暴力枚举但数组长度稍大就会超时。这道题真正的价值在于让我们理解“排序为什么能改变问题的复杂度”——如果不排序三角形判定要写三条不等式排完序一条就够了。这一条不等式的简化直接催生了双指针解法。这篇文章适合刚接触双指针的读者也适合刷题时“看着答案能懂、自己写就卡壳”的人。我会从暴力解法一步步推导把指针为什么这样移动、计数为什么能这么算讲清楚最后再补上边界条件和拓展思路。1. 题目拆解三角形判定条件里的关键简化1.1 题目到底在问什么先明确输入和输出。假设数组是[2, 2, 3, 4]下标分别为0、1、2、3那么能组成三角形的三元组有(2,3,4)、(2,3,4)和(2,2,3)一共3个。注意这里的两个2来自不同下标所以算作两个不同的三元组。这是这道题的一个重要特征我们统计的是下标组合不是值组合。数组里有重复元素时它们占据不同位置必须分别计数。很多人在刚开始写的时候会想“去重”但在这一题里是错误方向。三角形的定义大家都熟三条边a, b, c必须满足任意两边之和大于第三边。也就是要同时满足a b ca c bb c a接下来是整道题最关键的一步。1.2 排序之后判定条件从三条变成一条如果数组无序判断三个数能否组成三角形确实要把三条不等式都检查一遍。但只要我们把数组排成升序假设三个数的下标满足i j k那么对应数值一定满足nums[i] nums[j] nums[k]。此时结论是只需要检查nums[i] nums[j] nums[k]就够了。为什么因为nums[i] nums[k] nums[j]必然成立——左边两个数都分别大于等于nums[j]它们的和当然更大。同理nums[j] nums[k] nums[i]也必然成立。唯一可能出问题的是两个较小边的和能否压过最大边也就是nums[i] nums[j]是否大于nums[k]。想通这一点问题就从“验证三边关系”变成了“找两个数的和大于某个目标值”。这是后续所有优化的地基。1.3 边长的隐含约束与整数特性题目通常给出的是正整数数组。如果出现0它永远不可能和其他边组成三角形因为0 某边 另一边在排序后几乎不可能满足除非另一条边为负但正整数场景下不存在。由于我们只判断两个较小边之和是否大于最大边0会自然被排除在合法组合之外不会引入计数错误。但负数需要注意。如果数组里允许负数排序后最大边可能不是右端元素双指针的正确性就受影响了。所以请先确认题目输入绝大多数在线判题平台的版本都限定为非负整数或正整数本文也基于这个前提。遇到带负数的变体需要另行讨论那不是我们这次的重点。2. 暴力三重循环能跑通但注定超时的起点2.1 三重循环的写法与复杂度拿到题目先做暴力解是完全正确的学习方式它能帮你验证对题意的理解。最朴素的三重循环是这样int triangleNumber(vectorint nums) { int n nums.size(); int ans 0; for (int i 0; i n; i) { for (int j i 1; j n; j) { for (int k j 1; k n; k) { if (nums[i] nums[j] nums[k] nums[i] nums[k] nums[j] nums[j] nums[k] nums[i]) { ans; } } } } return ans; }这里我用的是无序数组版所以要写满三条判断。它的复杂度是O(n^3)。当n等于100时循环体执行约16万次完全没问题当n等于1000时执行约1.66亿次本地跑已经能感受到明显延迟当n等于5000时直接是百亿级别在线判题平台不可能放行。2.2 暴力解法的真实临界点我实际测试过在普通笔记本上n在200左右暴力解可以肉眼无感完成n到500时就要等待一两秒了。所以暴力解法不是一无是处它适合用来做小数据量的答案验证。后面你写双指针解法时完全可以保留一个暴力函数用随机小数组对拍这是排错时极其有用的手段。2.3 排序已经能帮暴力解剪掉一大半判断如果在暴力三重循环前先给数组排序循环内的判断可以简化成一条sort(nums.begin(), nums.end()); for (int i 0; i n; i) { for (int j i 1; j n; j) { for (int k j 1; k n; k) { if (nums[i] nums[j] nums[k]) { ans; } } } }排序是O(n log n)三重循环依然是O(n^3)所以整体复杂度不变。但它让代码更清爽也让你意识到既然在升序数组里当nums[i] nums[j] nums[k]成立时更后面的k一定也成立那为什么不直接批量计数呢这已经是走向双指针的直觉了。3. 排序双指针用单调性把枚举压缩成线性扫描3.1 固定最大边问题就变成“两数之和大于目标”双指针解法的核心想法是枚举三角形中的最大边。把数组升序排序后从右往左遍历最大边nums[i]然后在它左侧区间[0, i-1]内找出所有满足两个数之和 nums[i]的二元组。为什么固定最大边而不是最小边因为一旦确定哪条边最大三角形判定的不等式就只剩下较小边之和 最大边这正是第1节推导的结论。如果固定最小边另外两边谁大谁小还得比较复杂度分析会很别扭。固定最大边是这道题双指针解法成立的根基。3.2 双指针的移动规则与计数方法假设当前枚举到最大边nums[i]令左指针l 0右指针r i - 1。比较nums[l] nums[r]与nums[i]如果nums[l] nums[r] nums[i]说明当前左指针指向的边太小即使和当前区间内最大的nums[r]相加都压不过nums[i]那么它和其他更小的元素更不可能组成三角形。于是l跳过这个左端点。如果nums[l] nums[r] nums[i]说明nums[l]和nums[r]能组成三角形。同时由于数组升序l到r-1之间的任何一个元素k都满足nums[k] nums[r] nums[i]。所以这一轮可以直接给答案加上r - l然后r--把右指针左移去检查更小的右边元素。这个计数方式加r - l而不是加1是整个算法效率的关键一次条件成立并不是只找到一个三角形而是找到[l, r-1]区间里所有能与nums[r]配对的左端点。我用一个具体的例子走一遍。数组[2, 2, 3, 4]排序后仍为[2, 2, 3, 4]。第一步i 3nums[3] 4l 0r 2。nums[0] nums[2] 2 3 5 4成立答案加2 - 0 2表示(2,3,4)和(2,3,4)两组。r--到1。第二步l 0r 1。nums[0] nums[1] 2 2 4 4不成立因为要求严格大于等于不行。l到1l r循环结束。第三步i 2nums[2] 3l 0r 1。nums[0] nums[1] 2 2 4 3成立答案加1 - 0 1即(2,2,3)。r--到0循环结束。合计答案3和暴力解一致。3.3 为什么计数r - l不会漏也不会重复这个解法最容易被质疑的地方就是计数方式。当nums[l] nums[r] nums[i]成立时我直接把r - l个三元组全部计入答案。凭什么是r - l关键在于升序数组的单调性。数组有序意味着nums[l] nums[l1] ... nums[r-1] nums[r]既然最小的nums[l]加上nums[r]都已经大于nums[i]那么任何一个位于(l, r)之间的元素nums[k]加上nums[r]必然也大于nums[i]。也就是说[l, r-1]区间内每个元素都可以和nums[r]、nums[i]组成三角形一共有r - l个。一口气计入答案后nums[r]已经完成使命r--进入下一轮。会不会重复计数不会。因为每个统计三元组都以某个确定的nums[i]作为最大边以某个确定的nums[r]作为第二大的边三元组中三条边的下标也被唯一确定下来。外层i从大到小遍历每个最大边只处理一次内层r从大到小移动每个第二大边只处理一次。所以不会有两个循环分支同时让同一个三元组进入答案。会不会漏也不会。如果nums[l] nums[r] nums[i]说明当前nums[l]太小即使配上区间内最大的nums[r]都不够配上任何其他元素更不可能所以这个l可以安全丢弃l。最终l和r相遇时所有可能的配对都已被检查过或批量计入没有遗漏。3.4 边界情况的循环终止条件内层循环是while (l r)。当l和r相遇说明当前最大边nums[i]的所有可能配对已经处理完外层i继续左移。外层循环从n-1遍历到2因为至少要有三条边枚举最大边时还要给两个较小边留出位置所以i 2才继续。如果数组长度小于3答案直接是0。这属于前置判断最好先写掉。4. 完整代码与边界条件让答案在细节里站稳4.1 双指针解法的完整实现把上面的思路翻译成代码C版本如下#include vector #include algorithm using namespace std; int triangleNumber(vectorint nums) { int n nums.size(); if (n 3) return 0; sort(nums.begin(), nums.end()); long long ans 0; for (int i n - 1; i 2; --i) { int l 0; int r i - 1; while (l r) { if (nums[l] nums[r] nums[i]) { ans r - l; --r; } else { l; } } } return (int)ans; }这里我用了long long存答案。题目如果给的是n 100000最大答案数量级是组合数C(n,3)约1.6e14远超32位整数的上限。虽然在线判题平台有时会把答案限制在int范围内但用long long是更稳妥的习惯。Python版本更短def triangleNumber(nums): nums.sort() n len(nums) if n 3: return 0 ans 0 for i in range(n - 1, 1, -1): l, r 0, i - 1 while l r: if nums[l] nums[r] nums[i]: ans r - l r - 1 else: l 1 return ans4.2 我踩过的几个边界坑第一个坑把写成。三角形要求的是任意两边之和严格大于第三边。三边为2, 2, 4时2 2 4不能组成三角形。代码里如果用就会多算答案。这类错误在暴力解中也很容易犯而且往往用随机小数据都测不出来因为边界数据太少。建议专门构造一个包含[1,1,2]的用例去测。第二个坑外层循环起点写错。有人习惯从左往右枚举“最大边”结果把i当成最小边导致逻辑全部错位。一定要明确我们的i是当前枚举的三角形最大边的下标所以必须从数组右端开始。第三个坑忘记排序。没有排序时双指针的单调性前提不成立计数公式r - l完全失效。这不是“少了一行代码”的问题而是整个算法根基崩塌。我见过有人花了很久排查最后发现是排序被注释掉了。第四个坑重复元素导致计数混乱。我在第1节强调过这题按下标计数不按值去重。[2,2,3,4]里两个2分别参与构成两个不同的(2,3,4)。双指针解法天然支持这一点因为你是在处理下标不是对值做集合操作。千万不要在排序后额外写unique那是把正确方向往反方向带。4.3 用暴力解随机对拍排错最有效的手段双指针解法写完强烈建议不要直接提交先用暴力解对拍。做法很简单写一个暴力函数生成大量随机数组比如长度从3到20元素从1到50随机取值分别用暴力法和双指针法计算结果一旦不一致就打印出当前数组。这个法子能在几分钟内帮你定位绝大多数逻辑错误。我自己的习惯是把暴力函数保留在本地测试文件里当成参考答案用。对拍通过之后再提交到在线判题平台基本一遍过。5. 复杂度上限与同类题型的通用套路5.1 时间复杂度对比与最优性双指针解法的时间复杂度是O(n log n n^2)其中排序是O(n log n)两层循环是O(n^2)。实际运行时因为内层指针l和r总共加起来只移动O(n)步所以每个外层i对应的内层扫描是线性的最终就是O(n^2)。有人可能想用二分查找替代双指针固定两条边后用二分找第三个边的最大合法位置复杂度是O(n^2 log n)。这种做法在n较小时可读性也不错但比双指针多一个log n因子。数据量到10^5时O(n^2)已经是极限O(n^2 log n)基本不可用。值得说一句有效三角形计数是一个3SUM-hard问题。在一般的比较模型下它的复杂度下界就是O(n^2)不存在已知的亚二次算法。所以你不需要再追求比双指针更快的通用解法这个双指针方案已经是渐近最优。5.2 这类题的通用套路排序双指针把这道题抽象一下你会得到一个高频套路面对一个“找出所有满足某种大小关系的组合”的问题如果组合的对象是数组元素先排序然后用双指针利用单调性批量计数而不是逐个枚举。同样的套路在三数之和、最接近的三数之和、四数之和等题目里反复出现。它们的共同点是先排序让数组具备单调性。固定一个或两个元素把多维问题降维成两数问题。双指针根据和与目标值的大小关系移动小了就左移、大了就右移。如果你完整消化了有效三角形个数的推导过程再去看三数之和会轻松很多因为两者的指针移动逻辑本质上同一个思想利用有序性跳过那些必然不成立或必然全部成立的区间。5.3 工程场景中哪里会用到这类思维虽然“统计三角形个数”本身不太会直接出现在业务代码里但排序加双指针在很多真实场景都有影子。举两个例子。一个是碰撞检测里判断若干物体之间的距离是否小于阈值通常先按坐标排序再用滑动窗口缩小比较范围避免两两暴力比较。另一个是数据库查询中的区间连接两个有序集合做连接时双指针交替推进的归并逻辑本质上也是这个套路。算法题的训练价值恰恰在于把抽象出来的单调性思维迁移到这些工程问题里。我自己做了这么多年算法相关的工作最大的体会是遇到组合计数类问题先想清楚有没有单调性可以利用比一上来就写搜索重要得多。有效三角形个数这道题就是练习这种思维方式的最好入门题之一。最后再分享一个实用技巧如果你在面试中遇到这题先把“排序后只需判断小 中 大”这一点说出来再往下讲指针移动。一开始就把这个关键简化点讲透会让面试官确信你不是背题而是真的理解了问题本质。这点和刷题一样重心永远在“为什么”而不是“怎么记”。