原题
给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。
示例1:
输入: [2,2,3,4] 输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意:
- 数组长度不超过1000。
- 数组里整数的范围为 [0, 1000]。
解法
思想
三角形的某两边之和必须大于第三边且两边之差小于第三边
方法:
- 暴力:获取所有3元组,判断能否构成三角形
- 动态规划:先给数组排序,任意两个较小边之和必须大于第三边。
对于数组[1,3,4,5,6],先将最大边指向6,一最小边i指向1,一最小边j指向5,如下图所示。

1+5不大于6,可以将最小边往后移一格。

如图所示,此时3+5大于6,可以组成三角形,而因为数组是排序过的,则最小边再向后移最小两边之和也是大于第三边的,所以此时可以把总数加上j-i
,然后把i还原回数组头部,j向前移一格
重复之前步骤,1+4不大于6,i向后移一格,3+4大于6,总数加上j-i
。

代码
- 暴力
class Solution {
public int triangleNumber(int[] nums) {
int count = 0;
for(int i = 0;i<nums.length-2;i++){
for(int j = i+1;j<nums.length-1;j++){
for(int n = j+1;n<nums.length;n++){
if(nums[i]+nums[j]>nums[n]&&Math.abs(nums[i]-nums[j])<nums[n]) count++;
}
}
}
return count;
}
}
- 动态规划
class Solution {
public int triangleNumber(int[] nums) {
int count = 0;
Arrays.sort(nums);
for(int n = nums.length-1;n>=2;n--){
int i = 0;
int j = n-1;
while(i<j){
if(nums[i]+nums[j]>nums[n]) {
count+=(j-i);
j--;
}else{
i++;
}
}
}
return count;
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode611-%e6%9c%89%e6%95%88%e4%b8%89%e8%a7%92%e5%bd%a2%e7%9a%84%e4%b8%aa%e6%95%b0/