程序计算C ++中有效三角三元组的数量

假设我们有一个数字数组,我们必须找到从数组中选择的三边形的数量,如果将其作为三角形的边长,则可以形成三角形。因此,如果输入类似于[2,2,3,4],则结果将为3,因为使用第一个2的三个三元组[2,3,4]使用第二个[2,3,4],以及[2,2,3]。

为了解决这个问题,我们将遵循以下步骤-

  • ret:= 0,n:= num的大小,对num进行排序

  • 对于范围在n − 1到0的i

    • 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

    以上是 程序计算C ++中有效三角三元组的数量 的全部内容, 来源链接: utcz.com/z/360155.html

    回到顶部