题目地址（611.有效三角形的个数）https://leetcode-cn.com/probl...题目描述给定一个非负整数数组，你的任务是计算可以构成三角形三边的三元组的数量。示例1：输入：[2,2,3,4]输出：3解释：有效组合为：2,3,4（使用第一个2）2,3,4（使用第二个2）2,2,3注意：数组长度不超过1000，数组的整数范围是[0,1000]。前置知识排序二分法三角边关系暴力法（超时）思路首先有一个数学前提：如果三条线段中任意两条之和大于第三条边，则这三条线段可以组成一个三角形。即给定三个线段a、b、c，如果满足a+b>c且a+c>b且b+c>a，则线段a、b、c可以组成三角形，否则不能。Leeknot中有一些题目是需要一些数学前提的，但是这些数学前提都比较简单，一般不会超过高中数学知识，也不是特别复杂。一般来说，小学和初中的知识就足够了。如果你在面试中遇到一个你不知道的数学前提，请向面试官寻求提示以进行尝试。重点是分析三角形各边的关系。三层循环决定了三个线段。代码代码支持：Pythonclass解决方案：defis_triangle(self,a,b,c):ifa==0orb==0orc==0:returnFalseifa+b>canda+c>bandb+c>a:返回True返回FalsedeftriangleNumber(self,nums:List[int])->int:n=len(nums)ans=0foriinrange(n-2):forjinrange(i+1,n-1):forkinrange(j+1,n):ifself.is_triangle(nums[i],nums[j],nums[k]):ans+=1返回ans复杂度分析时间复杂度：$O(N^3)$，其中N是数组的长度。空间复杂度：$O(1)$优化后的暴力法暴力法的时间复杂度为$O(N^3)$，其中$N$至多为1000。一般来说，$O(N^3)的算法3）$在数据量<=500时可以AC。在1000的量级上，需要考虑$O(N^2)$或者更好的方案。好的，我们开始吧。让我给你一个干品。其他博主不应该提及。原因可能是他们不知道，也可能是他们觉得说出来太幼稚了。由于我之前根据数据大小猜测解的复杂度区间是$N^2$,$N^2*logN$，所以不可能是$N$（WHY？）。降低时间复杂度的主要方法有：space-for-time和sort-for-time（我们一般使用基于比较的排序方法）。排序时间只适用于整体复杂度大于$O(NlogN)$的情况（原因不用多说了吧？）。这里，由于整体的时间复杂度是$O(N^3)$，自然而然的就想到了按时间排序。我们对nums进行排序后，发现is_triangle函数有一些判断是无效的defis_triangle(self,a,b,c):ifa==0orb==0orc==0:returnFalse#a+c>bandb+c>a都是无效判断，因为如果a+b>canda+c>bandb+c>a:returnTruereturnFalse总是true所以我们的目标就变成了找到a+b>c就够了，所以第三个循环可以提前退出。foriinrange(n-2):forjinrange(i+1,n-1):k=j+1whilek
