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