C++で有効な三角数

配列が非負の整数で構成されているとすると、私たちのタスクは、三角形の辺の長さとして三角形を作成できる配列から選択されたトリプレットの数を数えることです。したがって、入力が[2,2,3,4]の場合、結果は最初の2を使用して[2,3,4]、2番目の2を使用して[2,3,4]、[2,2]として3になります。 、3]。

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

• ret：=0、n：=numのサイズ、numの並べ替え
• n –1から0までの範囲のiの場合
  • 右：=i – 1、左：=0
  • 左<右
    • sum：=nums [left] + nums [right]
    • sum> nums [i]の場合、retを右–左に増やし、右を1減らし、それ以外の場合は左を1増やします
• return 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