Giả sử chúng ta có một mảng số, chúng ta phải tì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 vì có ba bộ ba [2,3,4] sử dụng số 2 đầu tiên, [2,3,4] sử dụng số 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 xuống 0
-
phải:=i - 1, trái:=0
-
trong khi trái
-
sum:=nums [left] + nums [right]
-
nếu sum> nums [i], thì tăng ret qua phải - trái, giảm sang phải 1, ngược lại thì tăng sang trái 1
-
-
-
trả lại ret
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