给定一个包含非负整数的数组,你的任务是计算从数组中选出的可以制作三角形的三元组数目,如果我们把它们作为三角形的边长。
样例
输入: [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;
}
网友评论