本文主要是介绍leetcode 611. 有效三角形的个数(优质解法),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
代码:
class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int length=nums.length;int n=0; //三元组的个数//c 代表三角形最长的那条边for (int c=length-1;c>=2;c--){int left=0;int right=c-1;while (left<right){if(nums[left]+nums[right]>nums[c]){n+=right-left;right--;}else {left++;}}}return n;}
}
题解:
首先我们要知道如何判断三条边是否可以组成三角形,假设我们有三条边 a,b,c,当 a+b>c && a+c>b && b+c>a 时,a,b,c 三条边就可以组成三角形,但很明显这样判断条件过多,其实我们还有一种判断方法:
当 a,b 为三条边中较小的两条边时,只要满足 a+b > c,就代表a,b,c 三条边可以组成三角形
我们在数组中获取参数时,如何知道获取的边是较小的两条边还是较大的一条边呢?可以先将数组进行排序,就可以将右边的数看作较大的一条边,在该数左边的区间找较小的两条边,来判断是否可以组成三角形
我们以数组 1,4,4,3,2 为例
经过排序以后数组变为 1,2,3,4,4
我们就以指针 c(nums.length - 1) 的数据作为构成三角形较大的一条边,现在我们要在该下标左边的区间选择两条边来组成三角形,让 L 指针指向 0 下标,R 指针指向 c-1 下标,两个指针代表此时选中的 a ,b 边,其中 1+4=5>4 代表是一组合格的数据,可以组成三角形
我们可以思考,L 指针指向的边是最小的边,最小的边加上此时 R 指针指向的边都可以大于第三边,那么 L 指针右边比它大的边加上此时 R 指针指向的边也一定是大于第三边的,所以我们可以得出以 R 指针指向的边作为 b 边,c 指针指向的边作为 c 边有 3组合格的数据,即 R - L 组 合格的数据
1 2 3 4 4
L R c
0 1 2 3 4
计算出此时 R 指针指向的边作为 b 边的所有情况以后,R 指针就可以向左移动
此时 1+3=4 <= 4 所以指向的 1,3,4 的三条边不符合要求
1 2 3 4 4
L R c
0 1 2 3 4
因为 a ,b边的和小了,但R 指针已经指向了目前最大的一条边,所以要让 L 指针向右移动,此时 2+3=5 > 4 所以有 R - L 组 合格的数据
1 2 3 4 4
L R c
0 1 2 3 4
计算出此时 R 指针指向的边作为 b 边的所有情况以后,R 指针就可以向左移动,当 R 指针与 L 指针指向同一个位置时,就代表以 c 指针指向的边作为 c 边的全部情况已经收集完毕,现在我们就需要将 c 指针向左移动,选择新的一条边作为 c 边,继续进行上述的操作
1 2 3 4 4
L c
R
0 1 2 3 4
当 c 指针移动到下标 2 的位置后,就代表所有的情况都收集完毕了
1 2 3 4 4
c
0 1 2 3 4
这篇关于leetcode 611. 有效三角形的个数(优质解法)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!