题目链接:611. 有效三角形的个数 - 力扣(LeetCode)
思路:
这道题要根据数组中的元素来判断能组成三角形的个数,
三边a、b、c要满足a+b>c,a+c>b,b+c>a这三个条件才能构成三角形。
当c>a,c>b时,我们只需要判断一个条件a+b>c是否满足就可以了,满足就能构成一个三角形。
所有我们可以先对数组进行排序
我们先选定最大的数作为c,让left=0,right在c的位置-1,
如果arr[left]+arr[right] > c,那么left和right中间这些>=left指向的数的元素和righ指向的数相加一定也是>c的,因此这些数和arr[right]、c一定能构成三角形。
然后left应该向左移动,再去判断移动后的arr[left]+arr[right]和c的关系。
如果arr[left]+arr[right] < c,那就把left向右移动,然后再去判断。
直到left和right相遇,我们就把所有c作为做大的数的所有情况判断完了,再把c左移,然后重复上面的情况。
因为要构成一个三角形,数组中至少要有3个数,所有c的位置做多只能到数组下标为2的位置。
代码:
public int triangleNumber(int[] nums) {
//排序
Arrays.sort(nums);
int result = 0;
for(int i = nums.length - 1; i >= 2; i--) //固定最大数
{
int left = 0, right = i - 1;
while(left < right){
if(nums[left] + nums[right]>nums[i]){
result += right - left;
right--;
}else{
left++;
}
}
}
return result;
}