C++의 유효한 삼각형 수

배열이 음이 아닌 정수로 구성되어 있다고 가정하고 삼각형의 한 변의 길이로 취하면 삼각형을 만들 수 있는 배열에서 선택한 삼중항의 수를 세는 것이 우리의 임무입니다. 따라서 입력이 [2,2,3,4]와 같으면 결과는 첫 번째 2를 사용하는 [2,3,4], 두 번째 2를 사용하는 [2,3,4], 그리고 [2,2]와 같이 3이 됩니다. ,3].

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

• ret :=0, n :=숫자 크기, 숫자 정렬
• n – 1에서 0까지 범위에 있는 i의 경우
  • 오른쪽 :=i – 1, 왼쪽 :=0
  • 왼쪽 <오른쪽
    • 합계 :=숫자[왼쪽] + 숫자[오른쪽]
    • 합계> 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