1. 有效三角形的个数
题目链接：
611. 有效三角形的个数 - 力扣（LeetCode）
https://leetcode.cn/problems/valid-triangle-number/description/
2. 题目解析
以示例1为例：
3. 优化
我们都知道，判断三角形的方法就是两边相加大于第三边，但是一个一个的对比实在太过麻烦，但是如果我们知道三个数的大小顺序，那么我们只需要判断前面两个较小的数相加等于第三个数就可以了
我们可以先对数组进行排序
解法1：暴力解法
我们可以看到如果不优化的话我们是需要套三层for循环的，那么时间复杂度就很复杂，而我们排序之后就只需要进行一次for循环再加上排序的时间复杂度、
4. 算法原理
算法2：利用单调性，使用双指针算法
当我们进行排序之后，我们选定最后一个（假设为c）最大值，再选第一个值a和b，判断两者相加是否大于c，如果大于c，那么说明a之后的值加上b都是大于c的
那么就可以直接下标相减得到有多少种情况，然后再让right--取判断下一个情况就可以了，然后我们就会发现a加上b小于c，那么说明a之后的值加上b都是小于等于c的
那么我们只需要将left++在重新进行一遍就可以了
然后一直重复这两个过程
但是我们上面的过程一直是在固定10这种情况进行的，当我们找到固定10的所有情况之后，我们只需要将10固定到9可以了，然后在新的区间再重复我们上面的过程就可以了
5. 代码
class Solution {
public:
int triangleNumber(vector<int>& nums) {
//优化排序
sort(nums.begin(),nums.end());
//双指针
int ret=0,n=nums.size();
for(int i=n-1;i>=0;i--)
{
int left=0,right=i-1;
while(left<right)
{
if(nums[left]+nums[right]>nums[i])
{
ret+=right-left;
right--;
}
else left++;
}
}
return ret;
}
};完结撒花~
