更合网站设计制作,旅游搜索网站开发,做黑彩网站图片,苏州聚尚网络科技有限公司有效三角形个数 .题目链接题目详情算法原理补充知识点双指针:对撞指针 我的答案 . 题目链接
有效三角形个数
题目详情 算法原理
补充知识点
有效三角形需要满足的条件:
abcacbbca 其实在满足1的时候,c是最大的,那么2和3是显然成立的,因此我们可以这样解题: 对… 有效三角形个数 .题目链接题目详情算法原理补充知识点双指针:对撞指针 我的答案 . 题目链接
有效三角形个数
题目详情 算法原理
补充知识点
有效三角形需要满足的条件:
abcacbbca 其实在满足1的时候,c是最大的,那么2和3是显然成立的,因此我们可以这样解题: 对数组进行排序,先找到一个最大的边,然后对这个边的左边进行遍历和校验,看看有哪两个边能够与这个边组成三角形,然后再对次最长的边进行校验,依次循环
双指针:对撞指针
这里校验另外两个小边与大边是否能够组成三角形,我们使用的是双指针算法:利用单调性,使用双指针来解决问题
当nums[left]nums[right]最长边的时候,也就是图中2910 这时left右边的数与right相加都会满足left910,所以这时满足条件的个数为right-left个,那么此时与right可以匹配的数已经校验完了,现在只需要将right–,进行下一次校验即可 当nums[left]nums[right]最长边的时候,也就是图中2510 这个时候,right左边的与left相加都会小于最长边,也就不满足构成有效三角形的情况,所以此时的left就已经没有了匹配的价值了,此时需要跳过当前left,即left,进行下一次判断 当最长边左边的区间都遍历完成之后,校验下一个最长边
我的答案
class Solution {public int triangleNumber(int[] nums) {int n nums.length;int ret 0;Arrays.sort(nums);for(int i n-1;i2;i--){int left 0;int right i-1;while(leftright){if(nums[left]nums[right]nums[i]){retright-left;right--;}else{left;}}}return ret;}
}
