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

本文主要是介绍算法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;}
}

这篇关于算法005：有效三角形的个数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---