教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载本篇技术指南围绕「刷穿 LeetCode」系列第 611 题展开完整讲解如何在给定数组中统计能组成三角形的三元组个数并给出从「排序 暴力枚举」到「排序 二分」再到「排序 双指针」的三层递进式解法配合 Java / C / Python 三种语言的可运行代码与复杂度分析。读完本文你将掌握「先排序、后枚举较大边再用二分或双指针压缩第三边查找范围」的组合优化套路这一思路同样适用于仓库中「二分」「双指针」专题下的其他计数类题目。题目描述与问题抽象这是 LeetCode 上的 611. 有效三角形的个数难度为中等Tag 为「排序」、「二分」、「双指针」。题目给定一个包含非负整数的数组统计其中可以组成三角形三条边的三元组个数。示例 1输入: [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3注意数组长度不超过 $1000$数组里整数的范围为 $[0, 1000]$。注意数组中允许出现重复值因此2,3,4会因为使用第一个或第二个2而被视为两组不同的三元组而2,2,3同样是合法组合。数据规模 $n \le 1000$ 意味着 $O(n^3)$ 量级在最坏情况下达到 $10^9$ 次判断存在超时TLE风险这为后面的二分与双指针优化提供了必要性。基本分析先排序再枚举避免重复计数判断三条线段能否构成三角形的充要条件是「任意两边之和大于第三边」。若直接对每个三元组判断三次不等式不仅计算量大还极易重复统计。根据题意我们需要统计所有符合 $nums[k] nums[j] nums[i]$ 条件的三元组 $(k,j,i)$ 的个数。为了防止统计重复的三元组我们可以先对数组进行排序然后采取「先枚举较大数在下标不超过较大数下标范围内找次大数在下标不超过次大数下标范围内找较小数」的策略。排序带来的两个关键收益去重天然完成排序后按「较大边下标 次大边下标 较小边下标」的约束枚举每个三元组只会被统计一次下标天然区分了元素顺序不等式判定简化设排序后 $i j k$下标此时三条边的大小关系为 $nums[k] \le nums[j] \le nums[i]$。由于 $nums[k] nums[j]$ 和 $nums[k] nums[i]$ 必然大于 $nums[i]$、$nums[j]$非负整数保证唯一需要验证的只剩最弱的一条$nums[k] nums[j] nums[i]$。由此原问题被化简为枚举最大边 $i$ 与次大边 $j$统计 $[0, j)$ 范围内满足 $nums[k] nums[i] - nums[j]$ 的 $k$ 的个数。这个「在有序前缀区间内统计满足单调条件的元素个数」的子问题正是二分与双指针大展身手的场景。解法一排序 暴力枚举O(n³)根据「基本分析」我们可以很容易写出「排序 三层循环」的实现。Java 代码class Solution { public int triangleNumber(int[] nums) { int n nums.length, ans 0; Arrays.sort(nums); for (int i 0; i n; i) { for (int j i - 1; j 0; j--) { for (int k j - 1; k 0; k--) { if (nums[j] nums[k] nums[i]) ans; } } } return ans; } }C 代码class Solution { public: int triangleNumber(vectorint nums) { int n nums.size(), ans 0; sort(nums.begin(), nums.end()); for (int i 0; i n; i) { for (int j i - 1; j 0; j--) { for (int k j - 1; k 0; k--) { if (nums[j] nums[k] nums[i]) ans; } } } return ans; } };Python 代码class Solution: def triangleNumber(self, nums: List[int]) - int: n, ans len(nums), 0 nums.sort() for i in range(n): for j in range(i - 1, -1, -1): for k in range(j - 1, -1, -1): if nums[j] nums[k] nums[i]: ans 1 return ans时间复杂度排序时间复杂度为 $O(n\log{n})$三层遍历找所有三元组的复杂度为 $O(n^3)$。整体复杂度为 $O(n^3)$空间复杂度$O(\log{n})$。该做法思路最直观但复杂度为 $O(n^3)$在 $n 1000$ 时接近 $10^9$ 次判断有 TLE 风险因此仅适合理解问题不适合作为最终提交版本。解法二排序 二分O(n² log n)根据「优化枚举的基本思路」可参见仓库 363. 矩形区域不超过 K 的最大数值和困难 中「枚举两个值优化找第三数的逻辑」的讨论要找符合条件的三元组一个切入点可以是「枚举三元组中的两个值然后优化找第三数的逻辑」。我们发现在数组有序的前提下当枚举到较大数下标 $i$ 和次大数下标 $j$ 时在 $[0, j)$ 范围内找符合 $nums[k] nums[j] nums[i]$ 条件的 $k$ 的集合时以符合条件的最小下标 $k$ 为分割点的数轴上具有「二段性」。令 $k$ 为符合条件的最小下标那么在 $nums[i]$ 和 $nums[j]$ 固定时$[0, j)$ 范围内下标大于等于 $k$ 的点集符合条件 $nums[k] nums[j] nums[i]$下标小于 $k$ 的点集合不符合条件 $nums[k] nums[j] nums[i]$。因此我们可以通过「二分」找到这个分割点 $k$在 $[k, j)$ 范围内即是固定 $j$ 和 $i$ 时符合条件的 $k$ 的个数。这里使用的二分模板是「寻找第一个满足条件的位置」当nums[mid] nums[j] nums[i]时说明mid及之后都满足条件收缩右边界r mid否则说明mid及之前都不满足移动左边界l mid 1。最终l r处即为分割点且需要额外验证nums[r] nums[j] nums[i]以处理「区间内一个都不满足」的边界情况。Java 代码class Solution { public int triangleNumber(int[] nums) { int n nums.length, ans 0; Arrays.sort(nums); for (int i 0; i n; i) { for (int j i - 1; j 0; j--) { int l 0, r j - 1; while (l r) { int mid l r 1; if (nums[mid] nums[j] nums[i]) r mid; else l mid 1; } if (l r nums[r] nums[j] nums[i]) ans j - r; } } return ans; } }C 代码class Solution { public: int triangleNumber(vectorint nums) { int n nums.size(), ans 0; sort(nums.begin(), nums.end()); for (int i 0; i n; i) { for (int j i - 1; j 0; j--) { int l 0, r j - 1; while (l r) { int mid l r 1; if (nums[mid] nums[j] nums[i]) r mid; else l mid 1; } if (l r nums[r] nums[j] nums[i]) ans j - r; } } return ans; } };Python 代码class Solution: def triangleNumber(self, nums: List[int]) - int: n, ans len(nums), 0 nums.sort() for i in range(n): for j in range(i - 1, -1, -1): l, r 0, j - 1 while l r: mid l r 1 if nums[mid] nums[j] nums[i]: r mid else: l mid 1 if l r and nums[r] nums[j] nums[i]: ans j - r return ans时间复杂度排序时间复杂度为 $O(n\log{n})$两层遍历加二分查找分割点的复杂度为 $O(n^2 \times \log{n})$。整体复杂度为 $O(n^2 \times \log{n})$空间复杂度$O(\log{n})$。关于二分查找中「二段性」判定模板的更系统讲解可参见仓库 Index/二分.md 专题页其中收录了 704. 二分查找、34. 在排序数组中查找元素的第一个和最后一个位置 等大量二分应用题目。解法三排序 双指针O(n²)更进一步我们发现当我们在枚举较大数下标 $i$并在 $[0, i)$ 范围内逐步减小下标由于数组有序也就是逐步减少值找次大值下标 $j$ 时符合条件的 $k$ 必然是从 $0$ 逐步递增的这是由三角不等式 $nums[k] nums[j] nums[i]$ 所决定的。原因在于固定 $i$ 后$j$ 从 $i-1$ 向 $0$ 递减则 $nums[j]$ 单调不增要维持 $nums[k] nums[j] nums[i]$$k$ 只能单调不减。于是 $k$ 指针只增不减整个内层循环中 $k$ 的总移动次数为 $O(n)$从而把第三层枚举彻底摊平。因此我们可以枚举较大数下标 $i$ 时在 $[0, i)$ 范围内通过双指针以逐步减少下标的方式枚举 $j$并在遇到不满足条件的 $k$ 时增大 $k$ 下标从而找到所有符合条件三元组的个数。Java 代码class Solution { public int triangleNumber(int[] nums) { int n nums.length, ans 0; Arrays.sort(nums); for (int i 0; i n; i) { for (int j i - 1, k 0; k j; j--) { while (k j nums[k] nums[j] nums[i]) k; ans j - k; } } return ans; } }C 代码class Solution { public: int triangleNumber(vectorint nums) { int n nums.size(), ans 0; sort(nums.begin(), nums.end()); for (int i 0; i n; i) { for (int j i - 1, k 0; j k; j--) { while (k j nums[k] nums[j] nums[i]) k; ans j - k; } } return ans; } };Python 代码class Solution: def triangleNumber(self, nums: List[int]) - int: n, ans len(nums), 0 nums.sort() for i in range(n): j, k i - 1, 0 while k j: while k j and nums[k] nums[j] nums[i]: k 1 ans j - k j - 1 return ans时间复杂度排序时间复杂度为 $O(n\log{n})$双指针找所有符合条件的三元组的复杂度为 $O(n^2)$。整体复杂度为 $O(n^2)$空间复杂度$O(\log{n})$。双指针做法是本题的最优解内层k指针全程只向右移动每个 $i$ 一轮下来 $k$ 至多移动 $j$ 次总摊还复杂度为 $O(n)$配合外层 $O(n)$ 的 $i$ 枚举得到 $O(n^2)$。这与 Index/双指针.md 专题中「排序 双指针」类题目的通用框架一致例如 15. 三数之和、18. 四数之和 等均采用了「先排序再用双指针收敛搜索范围」的套路。三种解法对比与选型建议解法核心思想时间复杂度空间复杂度适用场景排序 暴力枚举排序后三层循环枚举三元组$O(n^3)$$O(\log n)$仅用于理解题意$n$ 很小约 $\le 200$时可用排序 二分固定 $i$、$j$二分寻找分割点 $k$$O(n^2 \log n)$$O(\log n)$常规提交方案代码直观可迁移到任意「有序区间统计」问题排序 双指针固定 $i$$j$ 递减、$k$ 递增同步扫描$O(n^2)$$O(\log n)$本题最优解面试与竞赛首选从工程与面试视角给出的选型建议若追求最稳、最好写的代码选「排序 二分」两层枚举加上一个标准二分模板即可逻辑不易出错若追求最优复杂度选「排序 双指针」注意内层k只在循环开头重置为0或 Python 版本中在每轮 $i$ 内重置切不可在每轮 $j$ 中都重置k否则退化为 $O(n^3)$。仓库内的延伸阅读与练习路径本题在「刷穿 LeetCode」系列中被标记为 Tag「排序」、「二分」、「双指针」与该题同专题的题目及题解入口已归档在仓库的专题索引页中Index/二分.md收录 611. 有效三角形的个数、4. 寻找两个正序数组的中位数、33. 搜索旋转排序数组、704. 二分查找 等题目Index/双指针.md收录 611. 有效三角形的个数、15. 三数之和、16. 最接近的三数之和、18. 四数之和 等题目Index/排序.md收录各类基于排序的计数与配对题目。建议的练习顺序先用暴力枚举验证对题意的理解再依次实现二分版本与双指针版本并用题目给出的示例[2,2,3,4]期望输出3进行自测随后可以迁移到「三数之和」「四数之和」等姊妹题体会「排序 双指针」在同一框架下的复用逐步建立计数类问题的套路化解题能力。赞分享教程文档【免费下载链接】LogicStack-LeetCode公众号「宫水三叶的刷题日记」刷穿 LeetCode 系列文章源码项目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode点击查看免费下载相关推荐LeetCode 611 有效三角形的个数排序 单调指针的 O(N²) 优化解法全解LeetCode 611 有效三角形的个数排序 单调指针的 O N² 优化解法全解 导读 本篇技术指南围绕 LeetCode 611「有效三角形的个数」展文档教程知识库LeetCode 611 有效三角形的个数AlgoNote 算法通关手册排序 对撞指针高效统计三元组LeetCode 611 有效三角形的个数AlgoNote 算法通关手册排序 对撞指针高效统计三元组 本文是 AlgoNote「算法通关手册」中 06教程文档知识库LogicStack-LeetCode 刷穿系列LeetCode 16. 最接近的三数之和排序 双指针精讲LogicStack LeetCode 刷穿系列LeetCode 16. 最接近的三数之和排序 双指针精讲 本文是 LogicStack LeetCo教程文档上一篇5分钟上手Modly从下载、安装到首次生成本地3D模型的完整指南下一篇静态分析工具分类指南从编程语言到配置文件创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考