[LeetCode] 611. Valid Triangle Number
文章目录
Problem
Given an array consists of non-negative integers, your task is to count the number of triplets chosen from the array that can make triangles if we take them as side lengths of a triangle.
Example 1:
Input: [2,2,3,4]
Output: 3
Explanation:
Valid combinations are:
2,3,4 (using the first 2)
2,3,4 (using the second 2)
2,2,3
Note:
The length of the given array won't exceed 1000.
The integers in the given array are in the range of [0, 1000].
Solution
class Solution {
public int triangleNumber(int[] nums) {
//for triangle: a+b > c
if (nums == null || nums.length < 3) return 0;
Arrays.sort(nums);
int count = 0;
for (int i = 2; i < nums.length; i++) {
int l = 0, r = i-1;
while (l < r) {
if (nums[l] + nums[r] > nums[i]) {
count += r-l;
r--;
}
else l++;
}
}
return count;
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论