力扣 611 有效三角形的个数
首先需要知道如何判断 三个数是否能构成三角形。
假如 存在三个数 a < b < c,如果要构成三角形,需要满足:
a+b > c ; a + c > b ; b + c > a ; 任意两个数大于第三个数就可构成三角形。
其实不难发现,如果三个数 按照从大到小排序的话 , 只需满足 a+b > c 即可。
因此第一步首先对给定数组进行排序。
其次在固定最大的数作为一条边,再用双指针 left 指向第一个数 , right 指向固定的最大的数的前一个数。 当 nums[left] + nums[right] > 固定的最大数 , 将right指针右移 ;否则将指针 left 左移。
直至固定的最大数 是数组第三个数结束位置。(解题思路)
那么该怎么统计 有效三角形个数呢?
文章来源:https://www.toymoban.com/news/detail-626608.html
文章来源地址https://www.toymoban.com/news/detail-626608.html
class Solution {
public:
int triangleNumber(vector<int>& nums) {
//先给数组排序
sort(nums.begin(),nums.end());
int c = nums.size()-1;
int count = 0; // 记录有效三角形的个数
while(c>=2)
{
int left = 0, right = c-1;
while(left < right)
{
if(nums[left] +nums[right] > nums[c])
{
count += (right - left);
--right;
}else{
++left;
}
}
--c;
}
return count;
}
};
到了这里,关于刷题笔记 day4的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!