算法005——有效三角形个数

力扣——有效三角形个数点击链接跳转

判断三条边是否能组成三角形，大家第一时间想到的就是两边之和大于第三边

但是运用这个方法，我们需要判断三次，有一个更简单的方法，只需要判断一次

因为 C 已经是三边之中最大的了，无论加不加第二条边，都会比第三条边大，所以无需判断第一张图片中的后两种情况。

先对整个数组排序

排序完成后，我们先固定最大的数，然后枚举剩下两个数

如果按顺序枚举，时间复杂度太大，我们先用剩下的数的 最小值 与 最大值
此时有两种情况

1. a + b > c

此时，最小值 与 b 相加都大于 c，中间的数都 大于等于 a ,那么 中间的数 + b 都大于等于 c ，我们就不需要判断中间的数与 9 相加了，此时构成三角形的个数为 下标相减，那么 9 就没用了，让 right –

2. a + b <= c
   此时，最大值与 a 相加都小于等于 c，中间的数都小于等于 b ，那么 中间的数 与 a 相加都 小于等于 c，无需再判断 中间的数 与 a 相加，此时 a 没有用了，让 left++
   
   然后 c = 10 的情况判断完了，再判断 c = 9，再重复上述循环。

class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int count = 0;for(int i = nums.length - 1;i >= 2;i--){//最少有三个数int left = 0;int right = i - 1;while(left < right){if(nums[left] + nums[right] > nums[i]){count += right - left;right--;}else{left++;}}}return count;}
}

可以点个赞 让我忘本一下试试吗