C++で有効な三角形のトリプレットの数を数えるプログラム

数の配列があるとすると、三角形の辺の長さとして取ると、三角形を作ることができる配列から選択されたトリプレットの数を見つける必要があります。したがって、入力が[2,2,3,4]の場合、最初の2を使用する3つのトリプレット[2,3,4]、2番目の2を使用する[2,3,4]があるため、結果は3になります。 [2,2,3]。

これを解決するには、次の手順に従います-

• ret：=0、n：=numのサイズ、numの並べ替え

• n −1から0までの範囲のiの場合

  • 右：=i − 1、左：=0

  • 左<右

    • 合計：=nums[左]+nums[右]

    • sum> nums [i]の場合、retを右-左に増やし、右を1減らし、それ以外の場合は左を1増やします

• 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