一、题目描述
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
二、题目解析:
思路一:暴力枚举
暴力枚举无需多言,就是三个嵌套循环,思路最简单,复杂度也是最高O(N3)
思路二:利用单调性,使用双指针算法解决问题
我们要明确如何判断3个数能否构成三角形,第一种是任意两边之和要大于第三条边,但这种需要比较3次,比较繁琐;还有另一种只用比较一次就可以判读的方法:
将需要比较的三个数进行排序,我们只需要判断最小的两个数大于最大的数即可,另外两种不需要比较,因为另外两种肯定要加上最大值,显而易见,省去了比较的过程。
那排好序,如何用双指针的方法解决呢?
也是同样定义左右两个指针,
1、如果大于,说明最小的左指针加上都满足,那么比左指针大的数一定都满足,所以计算个数。然后右指针--,准备进行下一组的比较。
2、如果小于,说明右指针最大值都不满足,那么右边的数一定都不满足,所以需要left++,进行下一组的比较。
三、原码:
class Solution {
public:
int triangleNumber(vector<int>& nums) {
int sum = 0;
//先进行快排,递增顺序
sort(nums.begin(),nums.end());
//利用双指针解决问题
for(int i = nums.size()-1;i>=2;i--)//固定最大数
{
int left = 0;
int right = i-1;
while(left < right)
{
if(nums[left] + nums[right] > nums[i])
{
sum += right - left;
right--;
}
else
{
left++;
}
}
}
return sum;
}
};