admin管理员组文章数量:1034114
有效三角形的个数
题目链接：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的位置。
代码：
代码语言：javascript代码运行次数：0运行复制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;
}有效三角形的个数
题目链接：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的位置。
代码：
代码语言：javascript代码运行次数：0运行复制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;
}本文标签： 有效三角形的个数
版权声明：本文标题：有效三角形的个数 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://it.en369.cn/jiaocheng/1748118101a2256069.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论