题目解析

有效三角形的个数

判断三角形：任意两边之和大于第三边

需要重复计算：

知识点

1、需要判断三次：

2、只需要判断一次

已经知道这三个数的大小（先进行排序）
只需要判断
较小的两个数之和 是否 大于最大的数
就可以得出是否可以构成三角形

算法原理

1、先对整个数组进行排序
2、再去固定最大的数
3、在最大的数的左边区间内使用双指针算法进行统计符合条件的三元组的个数

编写代码

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        // 1、排序(从小到大)
        sort(nums.begin(),nums.end());
        // 2、去固定最大的数
        int i = 0;
        int n = nums.size();
        int sum = 0;

        for(i=n-1;i>=2;i--){
        // 3、right每次是从i-1开始（left从0开始）
            int left = 0;
            int right = i-1;

            while(left<right){
                if(nums[left]+nums[right]>nums[i]){
                    sum+=right-left;
                    right--;
                }else{
                    left++;
                }
            }
        }
        return sum;
    }
};