1.题目解析
给定一个包含非负整数的数组
nums，返回其中可以组成三角形三条边的三元组个数。
补充：
1.三角形的判断：假设有三条边按大小排序：
2.题目示例
示例 1:
输入: nums = [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使用第一个 2) 2,3,4 (使用第二个 2) 2,2,3示例 2:
输入: nums = [4,2,3,4] 输出: 4
分析题目可知是要算上重复的
3.算法分析：
①暴力枚举：
时间复杂度较高O(3*n^3)
三层for循环确定三条边，再定义一个计数器计算有小三角形的个数
//暴力枚举
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int count=0;
int len=nums.length;
for(int i=0;i<len;i++)
{
for(int j=i+1;j<len;j++)
{
for(int k=j+1;k<len;k++)
{
if(nums[i]+nums[j]>nums[k])
{
count++;
}
}
}
}
return count;
}集美们，不用跑了，我帮你们试过了，过不了
解法二：
利用单调性和双指针的方法：
举个例子：
2，2，3，4，5，6，7，8，9，10
1.设置一个最大值
2.在最大数的左区间内，使用双指针和单调性的方法计算出有效三角形的个数
本宝宝建议你自己画一画，真正理解这个算法。
会出现两种情况：
①left+right>max count+=right-left right--
②left+right=<max lrft++
代码实现：
public int triangleNumber(int[] nums) {
int len=nums.length;
int count=0;
for(int i=len-1;i>=0;i--)
{
int max=nums[i];
int left=0;
int right=i-1;
while (left<right)
{
if(nums[left]+nums[right]>max)
{
count+=right-left;
right--;
}
else
{
left++;
}
}
}
return count;
}当然这个代码你是跑不过的，为什么呢？
因为你无法确定最大值，我举的栗子正好是我排过序的，若是没有排过序，不仅找不到最大值，还无用大学生的方法判断是否是有效三角形，所以一定要先排序(这都是姐走过的弯路)
public int triangleNumber(int[] nums) {
Arrays.sort(nums);
int len=nums.length;
int count=0;
for(int i=len-1;i>=0;i--)
{
int max=nums[i];
int left=0;
int right=i-1;
while (left<right)
{
if(nums[left]+nums[right]>max)
{
count+=right-left;
right--;
}
else
{
left++;
}
}
}
return count;
}本题完，欢迎指正
