Số tam giác hợp lệ trong C ++

Giả sử chúng ta có một mảng bao gồm các số nguyên không âm, nhiệm vụ của chúng ta là đếm số bộ ba được chọn từ mảng có thể tạo thành tam giác nếu chúng ta coi chúng là độ dài các cạnh của một tam giác. Vì vậy, nếu đầu vào là [2,2,3,4], thì kết quả sẽ là 3 là [2,3,4] sử dụng đầu tiên 2, [2,3,4] sử dụng thứ hai 2 và [2,2 , 3].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ret:=0, n:=kích thước của nums, sắp xếp nums
• đối với tôi trong phạm vi n - 1 giảm xuống 0
  • right:=i - 1, left:=0
  • trong khi bên trái
  • sum:=nums [left] + nums [right]
  • if sum> nums [i], sau đó tăng ret qua phải - trái, giảm sang phải 1, ngược lại tăng sang trái 1

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[2,2,3,4]

Đầu ra

3