双指针刷题(三)
2023-12-31 17:40:03
?所有算法文章链接(最底部)
1.有效三角形个数
力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
1.分析题意
给一个非负的数组,判断这个数组能组成多少个三角形。
2.解题思路
补充知识:已知三边a,b,c,三边大小依次递增,判断是否能构成三角形,仅需判断a+b>c,判断一次即可。
1.为了减少判断三角形的次数,将数组按升序排序。
2.固定最大的数
3.在最大的数左边的区间内采用双指针算法,统计三角形的个数。
4.只需判断left + right 是否大于 i,
如果left+right 大于i,说明在[left,right]这个区间内所有的元素都可以构成right-left个三角形,right--。
如果left+right小于等于i,说明[left,right]区间内不是所有的元素都可以构成三角形,left++,直到区间内所有元素都可以构成三角形。
5.最后在把最大元素定为9,继续重复以上过程。
代码编写
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());
int end = nums.size()-1;
int sum = 0;
for(int i = end;i >= 2; 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;
}
};
文章来源:https://blog.csdn.net/W2155/article/details/135316844
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!