欢迎阅读 欢迎来到「有效三角形的个数」题解之旅本文将带你从“统计能组成三角形的三元组”这一计数问题出发深入理解排序 双指针的经典应用并掌握如何通过固定最长边、双指针扫描较短边来高效统计满足不等式a b c的组合数。在开始之前建议你先了解题目背景这是 LeetCode 611 题给定一个非负整数数组nums要求返回可以组成三角形三条边的三元组个数顺序无关。三角形的条件是任意两边之和大于第三边排序后只需检查nums[left] nums[right] nums[i]其中nums[i]为最长边。暴力枚举 O(n3)O(n3) 不可行而排序 双指针可将复杂度降至 O(n2)O(n2)。明确学习目标掌握排序 双指针计数的核心流程——先对数组升序排序然后固定最长边从大到小遍历在剩余左侧区间中使用双指针left指向最小边right指向次大边统计满足不等式的组合数。理解一次性累加的技巧若nums[left] nums[right] nums[i]则left到right-1的所有值与nums[right]组合都有效直接加上right - left并熟练处理边界情况和重复元素。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [2,2,3,4]输出3。本文将从问题转化、排序 双指针策略设计、计数优化批量累加到代码实现层层递进。即使你对双指针还不熟悉我们也会从“把最长边固定然后看两条短边能不能凑够”这一直觉出发让你轻松抓住核心思想——排序后固定最长边用双指针在左侧快速数出所有满足两边之和大于第三边的组合。现在让我们一起在数组中数出所有能组成三角形的三元组吧 一.题目611. 有效三角形的个数 - 力扣LeetCode​ 欢迎来到「移动零」题解之旅本文将带你从“将所有零移到数组末尾同时保持非零元素顺序”这一数组操作问题出发深入理解双指针快慢指针的经典应用并掌握如何原地修改数组实现高效的一次遍历。在开始之前建议你先了解题目背景这是 LeetCode 283 题给定一个数组nums要求将所有0移动到数组末尾并保持非零元素的相对顺序不变且必须原地操作不能复制新数组。这是数组操作中的基础题也是双指针思想的入门经典。明确学习目标掌握双指针解法——维护一个“慢指针”指向已处理好的非零序列的末尾用“快指针”遍历数组遇到非零元素则交换或覆盖到慢指针位置最后将剩余位置填零。理解为什么这种“只关心非零元素遇到零就跳过”的策略能保持相对顺序并熟练处理边界如全零数组或全非零数组。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [0,1,0,3,12]输出[1,3,12,0,0]。本文将从问题转化、双指针策略设计快慢指针详解、代码模拟到复杂度分析层层递进。即使你对双指针还不熟悉我们也会从“用慢指针记录非零元素应该放的位置”这一直觉出发让你轻松抓住核心思想——快指针负责探路慢指针负责记录所有非零元素依次往前靠零自然被挤到后面。现在让我们一起把零“搬运”到末尾让数组焕然一新吧 二.做题思路一、问题分析前置分析给定一个非负整数数组要求返回可以组成三角形的三元组个数。三角形条件任意两边之和大于第三边。核心转化排序后固定最长边nums[i]只需判断两条较短边之和是否大于nums[i]。这样将问题转化为在有序数组中寻找满足a b c的对数。二、算法策略排序 双指针第一步对数组nums进行升序排序。第二步固定最长边nums[i]从i n-1开始往前遍历最长边至少需要两个较小边所以i 2。第三步在[0, i-1]范围内使用双指针left和right若nums[left] nums[right] nums[i]则说明从left到right-1的任意k都与nums[right]满足条件因为nums[k] nums[left]因此可以直接累加right - left然后right--。否则left尝试增大两数之和。第四步遍历结束返回累加的总数。三、正确性说明简单版本排序后对于固定的最长边nums[i]只需求出有多少对较小的数满足a b nums[i]。使用双指针时若当前left和right满足条件则所有介于left和right-1之间的元素与nums[right]搭配也都满足因为数组有序左侧数越大和越大因此一次性累加right-left个组合不会漏解。若当前和不满足则必须增大左指针因为右指针已经最大只能通过增加左值来满足条件。该策略遍历所有可能的(left, right)对不重不漏因此正确。四、实现细节边界防护先对nums排序时间复杂度 O(n log n)。外层循环for (int i n - 1; i 2; --i)固定最长边。内层双指针left 0, right i - 1。若nums[left] nums[right] nums[i]则sum right - left; right--;否则left。注意nums中可能包含 0但三角形要求边长 0排序后若nums[left]0和仍可能等于最长边不会满足条件因此逻辑依然正确。时间复杂度 O(n²)空间复杂度 O(1)。五、返回值目标映射返回sum即有效三角形的总个数。三.代码class Solution { public: int triangleNumber(vectorint nums) { // 算法思路先对数组进行升序排序。 // 固定最长边 nums[i]从大到小遍历然后使用双指针 left 和 right 在 [0, i-1] 范围内寻找满足 // nums[left] nums[right] nums[i] 的对数。 // 由于排序后 left right若 nums[left] nums[right] nums[i] // 则对于所有 k ∈ [left, right-1]都有 nums[k] nums[right] nums[i]因为 nums[k] nums[left] // 因此可以直接加上 (right - left) 个三角形然后 right-- 继续检查更小的边。 // 若 nums[left] nums[right] nums[i]则 left 尝试增大左边。 sort(nums.begin(), nums.end()); // 升序排序 int n nums.size(); int sum 0; // 记录有效三角形的总数 // 固定最长边从数组末尾向前遍历因为排序后最大的在最后 for (int i n - 1; i 2; i--) { int left 0; // 左指针指向最短边 int right i - 1; // 右指针指向第二长边 // 在 [left, right] 区间内查找满足三角形不等式的组合 while (left right) { // 如果两条短边之和大于最长边则构成三角形 if (nums[left] nums[right] nums[i]) { // 因为 nums[left] 到 nums[right-1] 中的任意元素与 nums[right] 组合 // 其和都 nums[left] nums[right] nums[i]所以这些组合都有效。 // 因此直接加上 (right - left) 个有效组合。 sum right - left; right--; // 右指针左移尝试缩小右边界寻找更小的组合 } else { // 如果两条短边之和不大于最长边则需要增大左指针使得和变大 left; } } } // 返回有效三角形的总数 return sum; } };四、流程图 闭幕 恭喜你完成了「有效三角形的个数」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题先对数组进行升序排序然后固定最长边从大到小遍历使用双指针在左侧寻找满足nums[left] nums[right] nums[i]的组合。请问为什么要先排序如果不排序直接枚举三条边时间复杂度会变成多少当nums[left] nums[right] nums[i]成立时代码直接累加right - left个组合然后right--。为什么可以一次性加这么多这里的数学依据是什么如果数组中有重复元素如[2,2,3,4]代码中的left和right移动逻辑是否会重复计数或漏计请举例说明。数组元素包含0时如[0,1,1]0 1 1不成立因此不会计入三角形算法是否正确从三角形定义出发边长为 0 的边能否组成三角形本题的时间复杂度为O(n²)排序 O(n log n) 双指针 O(n²)如果数组长度n最大为1000这个复杂度是否可接受如果n扩大到10^5需要如何优化延伸挑战如果题目改为求能组成周长最大的三角形从nums中选出三条边使周长最大你如何利用排序快速求解如果要求统计所有满足nums[i] nums[j] nums[k]的三元组个数不要求i j k即无序组合本题的解法是否仍然适用需要注意什么如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案先排序是为了利用有序性固定最长边从而将三重循环降为双指针在单侧查找若不排序直接枚举三条边需 O(n³)排序后复杂度降为 O(n²)。当nums[left] nums[right] nums[i]时因为数组已排序对于任意k ∈ [left, right-1]都有nums[k] nums[right] nums[left] nums[right] nums[i]所以这些组合全部有效一次性累加right-left是基于排序的单调性保证的。重复元素不会导致漏计或重复因为双指针按索引位置区分元素每个三元组被唯一计数一次例如[2,2,3,4]中两个 2 被视为不同位置的元素分别计数算法正确。边长为0不能组成三角形任意两边之和必须大于第三边0 x x 不成立代码自然排除此类组合因此算法正确处理了 0 的情况。n1000时 O(n²) 1e6完全可接受若n10^5O(n²) 会超时需考虑更优的数学方法或近似算法但三角形计数问题本身在一般输入下 O(n²) 已是较优解法。延伸挑战答案挑战1排序后从大到小遍历最长边固定最长边后只需找到满足两边之和大于最长边的最大right然后用双指针找所有组合记录最大周长的三角形即可思路与本题高度一致只需额外记录周长最大值。挑战2本题默认i为最长边排序后索引最大隐含了有序三元组的计数即i j k。若要求无序组合即只关心三个数值不关心位置由于数组排序后每组合法三角形只会被统计一次因为最长边固定为最大索引因此解法无需改动依然适用。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨