通栏 网站模板,广东网站seo营销,成都龙泉建设局网站,石家庄做网站公司611. 有效三角形的个数
给定一个包含非负整数的数组 nums #xff0c;返回其中可以组成三角形三条边的三元组个数。
示例 1: 输⼊: nums [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使⽤第⼀个 2) 2,3,4 (使⽤第⼆个 2) 2,2,3 ⽰例 2: 输⼊: nums [4,2,3,4] 输出: 4 解…611. 有效三角形的个数
给定一个包含非负整数的数组 nums 返回其中可以组成三角形三条边的三元组个数。
示例 1: 输⼊: nums [2,2,3,4] 输出: 3 解释:有效的组合是: 2,3,4 (使⽤第⼀个 2) 2,3,4 (使⽤第⼆个 2) 2,2,3 ⽰例 2: 输⼊: nums [4,2,3,4] 输出: 4 解释 4,2,3 4,2,4 4,3,4 2,3,4 补充
给我们三个数, 判断是否能构成三角形?
需要满⾜任意两边之和要⼤于第三边。但是实际上只需让较⼩的两条边之和⼤于第三边即可。
若abc, 那么只需要判断一次a b c, 如果true, 那么可以构成; 反之则不能构成.
解法一: 暴力解法
暴力枚举所有三个数的组合, 然后判断a b c a c b b c a
for(i 0; i n; i) {for(j i 1; j n; j) {for(k j 1; k n; k) {check(i, j, k);}}
}时间复杂度: O(N3) 空间复杂度: O(1)
解法二: 利用单调性, 使用双指针算法
先对数组进行排序
根据判断三角形的优化方法, 我们可以固定一个最长边, 然后在比这条边小的有序数组中找出一个二元组, 使这个二元组之和大于这个最长边. 由于数组是有序的, 所以我们可以使用对撞指针来优化
设最长边枚举到i位置, 区间[left, right]是i左边的区间, 也就是比它小的区间 如果nums[left] nums[right] nums[i]: 就说明[left, right - 1]区间上的所有元素与nums[right]构成的二元组之和都大于nums[i]满足构成三角形条件的一共有right - left种此时right位置的元素所有情况都考虑完了, right--, 进入下一轮判断 如果nums[left] nums[right] nums[i]: 就说明[left 1, right]区间上所有的元素与nums[left]构成的二元组之和都小于等于nums[i]此时left位置的元素都考虑完了, left--, 进入下一轮循环
Java代码
class Solution {public int triangleNumber(int[] nums) {Arrays.sort(nums);int count 0;//固定最大的数for(int i nums.length - 1; i 1; i--) {int left 0;int right i - 1;while(right left) {if(nums[left] nums[right] nums[i]) {count right - left;right--;} else {left;}}}return count;}
}时间复杂度O(N2), 空间复杂度O(log2N)(快排占用的空间)
