合法的三角数

2018-11-24  本文已影响0人  AustinWeii

给定一个包含非负整数的数组,你的任务是计算从数组中选出的可以制作三角形的三元组数目,如果我们把它们作为三角形的边长。

样例
输入: [2,2,3,4]
输出: 3
解释:
合法的组合如下:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意事项
给定数组的长度不会超过 1000.
给定数组内的整数在 [0, 1000]内

我的答案:

 * @param nums: the given array
 * @return:  the number of triplets chosen from the array that can make triangles
 */
const triangleNumber = function (nums) {
    // Write your code here
    if(nums.length<3) return 0;
    nums=nums.sort();
    var count=0;
    for(var i=0;i<nums.length-2;i++){
        for(var m=i+1;m<nums.length-1;m++){
            var n=nums.length-1;
            while(m<n){
                //第一个数字a,第二个数字b,第三个数字c;当a+b>c成立时候,移动b的位置获得的数字都肯定大于等于b,所以a+b>c一定成立
                if(nums[i]+nums[m]>nums[n]){
                    count+=n-m;
                    break;
                }else{
                    n--;
                }
            }
        }
    }
    return count;
    
}



上一篇下一篇

猜你喜欢

热点阅读