611. 有效三角形的个数
文章目录
- 1.题目
- 2.思路
- 3.代码,
1.题目
611. 有效三角形的个数
给定一个包含非负整数的数组 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
2.思路
a+b>c，第一步先将数组排序，然后从后往前遍历，最后一个数字为c，让第一个数字为a，倒数第二个数为b，如果a+b>c说明a+1+b>c,a+2+b>c，中间一共有b-a个三角形，那么只需要–b进行下一轮判断，如果a+b<=c说明没有数组符合要求。
例如：2,2,3,4
a b c 此时a+b>c符合要求有b-a等于2,sum为2
2,2,3,4
a b c 此时a+b=c不符合要求
2,2,3,4
a b c 此时a+b>c符合要求有b-a等于1，sum为3
3.代码,
class Solution {
public:
int triangleNumber(vector<int>& nums) {
//排序
sort(nums.begin(), nums.end());
//查找
int sum = 0;
for(int i = nums.size()-1;i>0;--i){
int left = 0 , right = i-1;
while(left < right){
if(nums[left]+nums[right] > nums[i]){
sum+=right-left;
--right;
}else{
++left;
}
}
}
return sum;
}
};