C ++中的有效三角数
假设我们有一个由非负整数组成的数组,我们的任务是计算从数组中选择的三边形的数目,如果将其作为三角形的边长,则可以构成三角形。因此,如果输入类似于[2,2,3,4],则结果将是3,其中前2个为[2,3,4],[2,3,4]使用第二个2,而[2,2,3]。
为了解决这个问题,我们将遵循以下步骤-
ret:=0,n:=num的大小,对num进行排序
当我在n–1范围内下降到0
sum:=nums[left]+nums[right]
如果sum>nums[i],则从右向左增加ret,向右减少1,否则向左增加1
右:=i–1,左:=0
而左<右
返回ret
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h> using namespace std; class Solution { public: int triangleNumber(vector<int>& nums) { int ret = 0; int n = nums.size(); sort(nums.begin(), nums.end()); for(int i = n - 1; i >= 0; i--){ int right = i - 1; int left = 0; while(left < right){ int sum = nums[left] + nums[right]; if(sum > nums[i]){ ret += right - left; right--; }else left++; } } return ret; } }; main(){ vector<int> v = {2,2,3,4}; Solution ob; cout << (ob.triangleNumber(v)); }
输入值
[2,2,3,4]
输出结果
3