leetcode611-有效三角形的个数

原题

给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。

示例1:

输入: [2,2,3,4] 输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3

注意:

  1. 数组长度不超过1000。
  2. 数组里整数的范围为 [0, 1000]。

解法

思想

三角形的某两边之和必须大于第三边且两边之差小于第三边

方法:

  1. 暴力:获取所有3元组,判断能否构成三角形
  2. 动态规划:先给数组排序,任意两个较小边之和必须大于第三边。

对于数组[1,3,4,5,6],先将最大边指向6,一最小边i指向1,一最小边j指向5,如下图所示。

leetcode611-有效三角形的个数

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

leetcode611-有效三角形的个数

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

重复之前步骤,1+4不大于6,i向后移一格,3+4大于6,总数加上j-i

leetcode611-有效三角形的个数

代码

  1. 暴力
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;
    }
}
  1. 动态规划
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/