算法005：有效三角形的个数

. - 力扣（LeetCode）. - 备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。https://leetcode.cn/problems/valid-triangle-number/

要组成三角形的三条边，需要保证，两边之和大于第三边。

要求的是找出三个数，这三个数可以组成一个三角形。（找出这三个数的个数，有多少个三个数）

本题使用相向双指针来完成。

在题目所给的一连串数字中，我们可以把它排成从左到右依次递增的数组。此时，左边的第一个数就是左指针，右边倒数第二个数是右指针。

我们只需要手动计算，left 和 right 相加，和最右边的6比较，是否能组成三角形。

如果可以，就意味着left的右边一直到right左边一位，和right相加都是可以大于6的。

于是让ret += right - left

如果不行了，则让left向右边移动一位，重复上面的操作，一直到right和left相遇。

那么代码就很好处理了：

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int ret = 0;
        int n = nums.length - 1;
        for(int i = n ; i >= 2 ; i--){
            int left = 0;
            int right = i - 1; 
            while(left < right){
                if(nums[left] + nums[right] > nums[i]){
                    ret += right - left;
                    right--;
                }else{
                    left++;
                }
            }
        }
        return ret;
    }
}