企业官网建设流程全解析

1. 题目拆解与暴力解法的本质局限

“有效三角形个数”这道题，在LeetCode上的编号是611，很多刷题的朋友都叫它“算法5”，算是双指针专题里一道非常经典的入门进阶题。题目本身不复杂：给一个包含非负整数的数组，要求返回其中可以组成三角形的三元组个数。比如[2,2,3,4]，能组成三角形的组合有(2,3,4)和(2,2,3)两组，答案就是2。

但题目越简单，坑往往越深。我第一次见到这道题的时候，第一反应就是三层循环暴力枚举，把每三个数都拎出来判断一次a + b > c。这个思路小学生都会，但它最大的问题不是错，而是慢——数组长度一旦超过1000，O(N^3)的时间复杂度直接就崩了，跑个中等规模的测试用例都要好几秒，更别提LeetCode上那些动不动上万长度的数据。很多刚刚开始刷题的朋友，就是卡在这一步：暴力解法写出来很容易，但提交超时，然后就开始怀疑人生。

你可能会想，既然三层循环太慢，那能不能先把数组排序，然后二分查找第三条边？这个思路方向是对的，但实现起来还是有点绕。真正好用的做法是排序加双指针，也就是我们常说的“剪枝算法”的一种应用——通过减少无效枚举，把时间复杂度压到O(N^2)。这也是面试官希望看到的解法：不是背答案，而是能讲清楚“为什么暴力枚举不可行，双指针为什么能省时间”。

先花点时间把暴力解法的本质看清楚。三层循环枚举三元组，判断条件nums[i] + nums[j] > nums[k]，其中i < j < k。这里有三个维度的无序枚举：外层定i，中层定j，内层定k。每次判断都要做一次加法比较，加起来就是C(n,3)次组合判断，数量级是n^3/6。当n = 5000的时候，这个数大概是200亿次操作，任何语言都扛不住。

暴力解法的另一个问题是它浪费了大量已经算过的信息。比如说，你先判断了(1, 2, 5)不行，然后下一个三元组(1, 2, 6)其实根本不用再算，因为如果1 + 2不大于5，那就更不可能大于6。但暴力枚举不会做这种推理，它只会机械地重复加法。这就是优化的突破口：能不能让内层循环“记住”上一次的结果，避免重复计算？

答案是能。这就是排序加双指针思想的起点。先把数组排好序，然后固定一条边，再用两个指针去扫描另外两条边的可能性，让内层循环从“逐个枚举”变成“区间统计”，一下就把一维的枚举压缩掉了。这里面没有高深的数学，核心就一句话：有序数组能让你通过指针的相对位置，直接跳过一整批无效组合。

很多人刷算法题有个误区，觉得只要把视频课看完了、题解背下来了就算会了。但像“有效三角形个数”这种题目，你只有亲手从暴力解法开始推演，一步步走过超时的坑，才能在面试里真正讲出“为什么”。下一节，我会把双指针的具体设计思路拆开讲清楚。

2. 排序加双指针：核心思路与推导过程

2.1 为什么排序是第一步

排序在这道题里的作用，不是为了让数组好看，而是给“剪枝”创造条件。想象一下，如果数组是乱序的，你固定了一个数作为最大边，剩下的两条边怎么选？没有任何规律可言，只能暴力配对。但排完序之后，数组变成单调递增，这时候如果nums[left] + nums[right]已经大于某个阈值，那么nums[left+1] + nums[right]也一定大于这个阈值——因为左边的数变大了，和只会更大。

这个单调性就是整个算法的基石。它让你能够用“区间长度”来代替“逐个数枚举”。具体来说，排序之后，我们可以固定k作为三角形的最长边，然后在[0, k-1]这个区间里找两个数，使它们的和大于nums[k]。只要满足这个条件，三边就一定能构成三角形，因为另外两个数都比nums[k]小，nums[k] + 任何一边一定大于第三边。

这里有个细节值得强调：很多人会把三个数排序后依次判断a + b > c && a + c > b && b + c > a，但如果你已经固定了c是最大值，那么后两个条件天然成立，根本不需要判断。所以问题被大大简化：只判断最小两条边之和是否大于最大边，这一步就是前面热词里提到的“暴力枚举算法”到“剪枝算法”的关键跃迁。

2.2 双指针怎么移动

现在进入最核心的部分：固定了最大边nums[k]之后，剩下的两个数怎么高效计数？

我用left指向区间的左端，right指向k-1，也就是当前区间的最后一个元素。初始时，left = 0，right = k-1。接下来分两种情况讨论：

• 情况一：nums[left] + nums[right] > nums[k]

  这说明left从当前位置到right-1的每一个数，跟nums[right]搭配，和都大于nums[k]。为什么？因为数组有序，nums[left]是当前区间里最小的那个数，它加nums[right]都已经大于nums[k]了，那比它大的nums[left+1]、nums[left+2]自然更满足条件。所以这一下就能确定right - left个有效组合，然后right--，继续往左收缩。

• 情况二：nums[left] + nums[right] <= nums[k]

  这说明当前left太小了，连跟区间里最大的nums[right]搭配都不够。那left再继续往右试探吗？不对，应该让left++，因为只有增大左边这个数，才有可能让和变大。注意不要动right，因为right已经是区间里最大的数了，如果left + right都不够，那跟更小的数搭配更不可能。

这个逻辑有点绕，我再用一个具体例子带大家走一遍。假设排序后的数组是[2, 2, 3, 4, 5, 8]，固定k = 5，也就是nums[5] = 8。初始left = 0（值为2），right = 4（值为5）。计算2 + 5 = 7，7不大于8，所以left++，现在left = 1（值为2）。2 + 5 = 7，还是不大于8，继续left++。left = 2（值为3），3 + 5 = 8，不大于8，继续left++。left = 3（值为4），4 + 5 = 9，大于8，命中！这时候right - left = 4 - 3 = 1，只有1组组合(4, 5, 8)，right--变为3。现在left = 3，right = 3，指针相遇，结束内层循环。所以固定k=5时，一共只有1组有效三角形。

这个例子比较简单，我们再换一个有多个组合的。数组[2, 3, 5, 9, 10, 14]，固定最大边14（下标5）。初始left = 0（2），right = 4（10），2+10=12 <= 14，left++。left = 1（3），3+10=13 <= 14，left++。left = 2（5），5+10=15 > 14，命中！此时right - left = 4 - 2 = 2，也就是(5,10)和(9,10)两组，right--变成3。现在left = 2，right = 3，5+9=14 <= 14，left++。left = 3，跟right相等，结束。所以最大边14时，总共贡献2组有效组合。

这回你看出门道了吧？每次命中，一次性计数right - left，不是一个个去枚举。内层循环最多走n步，每一步要么left++要么right--，所以内层是O(N)。外层还要遍历所有k，因此总复杂度是O(N^2)。从O(N^3)到O(N^2)，这就是排序加双指针的威力。

2.3 边界条件和细节禁忌

最容易被忽略的边界条件是：数组长度小于3时，直接返回0。这个判断必须在排序之前做，否则后面访问下标k-2会越界。另外，三角形要求三边都是正数。题目里如果出现0，那0跟任何两个正数都无法组成三角形，因为0 + a > b在b >= a时不成立。不过好消息是，我们用的判断逻辑nums[left] + nums[right] > nums[k]会自动把0排除掉——0加任何数都不大于最大边，指针会一直移动直到跳过0。

还有一个细节是重复元素。数组里出现重复值不用慌，排序后重复元素会相邻排列。双指针算法基于“区间计数”，天然能处理重复值。比如[2, 2, 2, 2, 2]，固定任意一个最大边，left和right之间的每个组合，只要nums[left] + nums[right] > nums[k]，都会一次性计数进去，不会漏也不会重。

有人会问：固定最大边之后，为什么不固定最小边？其实也可以，但代码逻辑会变得别扭。固定最大边的优势在于，三角形的最长边是明确的，判断条件缩减成一个；如果固定最小边，你就要同时考虑两条边谁是次大边，逻辑分支变多，出错概率上升。我们写代码要的是简单可靠，不是花哨。

3. 代码实现与核心细节对比

3.1 Java实现与关键点注释

Java是LeetCode上用得最多的语言之一，我先用Java写一版标准答案：

class Solution { public int triangleNumber(int[] nums) { if (nums == null || nums.length < 3) { return 0; } Arrays.sort(nums); int count = 0; int n = nums.length; for (int k = n - 1; k >= 2; k--) { int left = 0; int right = k - 1; while (left < right) { if (nums[left] + nums[right] > nums[k]) { count += right - left; right--; } else { left++; } } } return count; } }

这段代码有几个地方值得专门说一下。

第一个是count += right - left的原理。当nums[left] + nums[right] > nums[k]时，left之后的所有元素（一直到right-1）都能和nums[right]、nums[k]组成三角形，数量正好是right - left。这是我前面反复强调的单调性推论，也是整个算法省时间的核心。如果你在这里写成count++然后只移动right，那算法就退化成近似暴力了，复杂度会重新飙上去。

第二个是外层循环的方向。我选择从数组末尾往前面遍历k，也就是优先枚举最大的边。为什么不是从前往后？因为一旦k从小到大，后面的元素可能是前面元素的最大边，也可能不是，逻辑边界不清晰；从大到小，每次k都是当前区间里绝对的最大值，判断条件最干净。

第三个是right--之后不需要重置left。有人会担心，right变小了，原本和right匹配过的那些left值还能用吗？答案是能。因为nums[right_new] <= nums[right_old]，之前left + right_old > nums[k]的那些组合，换成更小的right_new可能就不满足了。所以left不能从0重新开始，而是要保持当前位置继续向右探索。这个细节如果你不注意，写出来的代码会重复计数，或者漏掉组合。从0重新开始是最常见的错误写法，切记不要这么做。

3.2 C++和Python的差异提示

C++版本基本可以照搬Java，只需要把数组换成vector，注意一下类型：

class Solution { public: int triangleNumber(vector<int>& nums) { if (nums.size() < 3) return 0; sort(nums.begin(), nums.end()); int count = 0; int n = nums.size(); for (int k = n - 1; k >= 2; --k) { int left = 0, right = k - 1; while (left < right) { if (nums[left] + nums[right] > nums[k]) { count += right - left; --right; } else { ++left; } } } return count; } };

C++里唯一需要留神的是int溢出问题。当数组元素很大，比如接近INT_MAX时，nums[left] + nums[right]可能溢出变成负数，导致判断条件出错。这个问题在Java和C++里都存在。我的建议是先把数转成long再相加，或者干脆在排序之后，如果最大元素超过INT_MAX / 2，就用long类型做加法。实际面试中，通常测试数据不会这么极端，但养成好习惯总没错。

Python版本可以写得更简洁，而且Python的int是任意精度的，没有溢出问题：

class Solution: def triangleNumber(self, nums: List[int]) -> int: if len(nums) < 3: return 0 nums.sort() count = 0 n = len(nums) for k in range(n - 1, 1, -1): left, right = 0, k - 1 while left < right: if nums[left] + nums[right] > nums[k]: count += right - left right -= 1 else: left += 1 return count

Python这道题的写法基本是Java的直译。这里值得一提的点是，Python的切片操作很容易让人写出nums = sorted(nums)产生新列表，白白占用额外内存。直接在原数组上.sort()更省空间。这看起来是小细节，但面试官如果问“空间复杂度”，用sorted()返回新数组的话，空间复杂度就是O(N)而不是O(1)，这就是扣分项了。

3.3 复杂度对比：为什么O(N^2)是这道题的最优解

我们来做一个复杂度对照表，用最直观的方式展示各种解法的差距：

排序加二分查找是另一个常见思路：固定两条短边，二分找第三条边的位置，复杂度是O(N^2 log N)。这个思路能过大部分测试用例，但遇到特别大的数组，比如N = 10000，N^2 log N大概是13亿次操作，会非常吃力。双指针把这个 log 因子也消掉了，N = 10000 时只需要1亿次操作，完全在可接受范围内。

还有一个有趣的细节：这道题的最优解法为什么不是O(N)？因为三角形计数问题本质上需要考察所有可能的三边组合关系，而组合的数量是C(N,3)，虽然我们用剪枝避免了逐一枚举，但这个下界决定了至少需要O(N^2)级别。面试时如果有人问你“还能不能再优化”，你可以从这个角度回答，说明双指针已经是渐近最优解。

很多教程把这道题归类于“排序算法”的延伸应用，因为排序是前提。但更准确地说，它是“数据结构与算法”里双指针技巧的典型代表。双指针技巧的应用场景非常广泛，包括两数之和、三数之和、盛最多水的容器等等。掌握了这道题，等于掌握了一把能解决一类题型的钥匙。

4. 常见问题与实战排查记录

4.1 为什么我的三指针解法会漏计数

我在自己刷题和带朋友刷题的过程中，发现最常见的错误是这样写的：固定k，然后left从0开始，right从k-1开始，当nums[left] + nums[right] > nums[k]时，直接count += right - left; right--。这跟我给出的标准写法是一样的。问题出在else分支：有人把left++和right--同时做了，导致漏计数。

举个例子，数组[1, 2, 3, 4, 5]，固定k=4（值为5）。初始left=0（1），right=3（4），1+4=5，不大于5，走else。如果同时移动 left 和 right，变成left=1（2），right=2（3），2+3=5，不大于5，再同时移动，left=2，right=1，退出循环。整个过程一个有效组合都没找到。但实际上(2,4,5)是有效组合：2+4=6 > 5。

为什么同时移动会漏？因为left++和right--会导致搜索空间瞬间收缩，跳过了一大批中间状态。正确的做法是每次只移动一个指针：当和不够大时，说明left太小，只需要left++；当和足够大时，计数并收缩右边界。记住这条铁律：双指针的每次迭代只移动一个指针，除非你明确知道另一个指针永远不会再有用。

4.2 数组里有负数怎么办

题目描述说的是非负整数，但实际面试中，面试官可能会追加一句“如果把负数加进去呢”？这时候直接套用上面的代码会出错。原因是，负数加正数可能很小，甚至两个负数相加更小，排序后的单调性虽然还在，但“最小边之和大于最大边”这个推理不再成立——因为最大边可能是正数，负数加任何数都可能不大于它，但负数加负数更不可能。三角形边长定义上就是非负的，所以负数场景本身就是伪命题。如果你遇到这个追问，正确的回应是：先过滤掉所有非正数，只保留正数部分再跑双指针。这也算是一个小trick，面试官会欣赏你考虑问题的周全性。

4.3 大数组性能测试的实际表现

我本地做过一组性能对比测试，用随机生成的数组，元素范围在1到1000之间：

这个表格很直观：N=2000时，暴力已经慢到让人怀疑人生，双指针还在毫秒级别。LeetCode的测试用例通常有N=10000以上的极端情况，这也是为什么暴力解法一定会超时。实测下来，双指针解法不仅稳，而且代码本身只有十几行，几乎没有调优空间，属于标准答案级的解法。

4.4 面试场景的延伸追问

面试官可能会在你看似完美地讲完解法之后，追加几个问题。最常见的是：如果不允许排序，有没有办法做？这个问题其实是在考察你对时间和空间权衡的理解。如果不排序，可以用哈希表记录每个数出现的次数，然后枚举两条边，用查找表判断第三条边是否存在。但这样做有两个问题：第一，无法直接判断“大于”关系，只能判断“存在”；第二，重复元素的组合计数非常麻烦。所以排序几乎是必须的预处理步骤。

另一个追问是：如果数组很大，内存装不下怎么办？这就涉及外部排序和分块处理的思路了。你可以回答：先外部排序，再用多路归并分段处理双指针逻辑。不过这种问题在面试中属于开放性讨论，重点是展示思路，而不是真的写出分布式代码。

4.5 实战排查口诀

我自己刷题总结了一段口诀，分享出来：

• 先判长度，小于三直接返回0
• 排序记住：原地排，别用新数组
• 外层从后往前，固定最大边
• 内层双指针，只移动一个指针
• 命中计数加区间长度，别一个个加
• 加和用long，防溢出

这段口诀基本覆盖了所有容易出错的地方。每次写这道题之前默念一遍，正确率能提高不少。如果你是在准备算法工程师面试，建议不光要会写，还要能讲清楚每一步的原理。面试官看重的不是你会背答案，而是你能不能把双指针的单调性证明讲明白。

我个人在实际操作中的体会是，这道题最值得记的并不是代码本身，而是“区间计数”这个思想——当你在有序数组里发现某个范围的元素都满足条件时，直接加范围长度而不是遍历范围。这个思想在很多题目里都会用到，比如统计逆序对、滑动窗口最大值、以及部分前缀和题目。把这道题吃透，后面做双指针系列会顺畅很多。

最后再分享一个小技巧：如果写完代码之后不确定对不对，可以用一个极端的测试用例来验证——全相同元素的数组，比如[5,5,5,5,5]。这时任意三个数都能组成三角形，答案应该是C(5,3) = 10。跑一下代码，看结果是不是10。如果是，说明逻辑基本稳；如果不是，多半是计数逻辑出了问题。这个小技巧能帮你快速定位bug，省下大量调试时间。