给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。
示例 1:
输入: [2,2,3,4]
输出: 3
解释:
有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
注意:
数组长度不超过1000。
数组里整数的范围为 [0, 1000]。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/valid-triangle-number 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public:
int triangleNumber(vector<int>& nums) {
if(nums.size() < 3)
return 0;
sort(nums.begin(), nums.end());
int i, j, k, count = 0;
for(i = nums.size()-1; i >= 2; --i)
{
j = i-1;
k = 0;
while(k < j)
{
if(nums[k]+nums[j] <= nums[i])// nums[i] 最大
++k;
else
{
count += j-k;
--j;
}
}
}
return count;
}
};