C++에서 유효한 삼각형 세 쌍의 수를 계산하는 프로그램

숫자 배열이 있다고 가정하고 삼각형의 한 변의 길이로 취하면 삼각형을 만들 수 있는 배열에서 선택된 세 개의 삼각형을 찾아야 합니다. 따라서 입력이 [2,2,3,4]와 같으면 첫 번째 2를 사용하는 세 개의 트리플렛 [2,3,4], 두 번째 2를 사용하는 [2,3,4]가 있으므로 결과는 3이 됩니다. [2,2,3].

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• ret :=0, n :=숫자의 크기, 숫자 정렬

• 범위 n − 1에서 0까지의 i에 대해

  • 오른쪽 :=i − 1, 왼쪽 :=0

  • 왼쪽 <오른쪽

    동안

    • 합계 :=숫자[왼쪽] + 숫자[오른쪽]

    • sum> nums[i]이면 ret를 오른쪽 - 왼쪽으로 증가시키고 오른쪽으로 1만큼 감소시키고 그렇지 않으면 왼쪽으로 1 증가

• 리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

#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