免费创建个人博客网站东莞专业微网站建设价格

给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。

示例 1:

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

输入: nums = [4,2,3,4]
输出: 4

提示:

1 <= nums.length <= 1000
0 <= nums[i] <= 1000

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int res = 0;for(int i = nums.size() - 1; i > 1; i -- ) {int l = 0, r = i - 1;while(l < r) {if(nums[l] + nums[r] > nums[i]) {res += r - l;r --;} else {l ++;}}}return res;}
};

class Solution {
public:int triangleNumber(vector<int>& nums) {sort(nums.begin(), nums.end());int res = 0;for(int i = nums.size() - 1; i > 1; i -- ) {for(int l = 0, r = i - 1; l < r; r --) {while(l < r && nums[l] + nums[r] <= nums[i]) l ++;res += r - l;}}return res;}
};