ধরুন আমাদের কাছে সংখ্যার একটি অ্যারে আছে, আমাদেরকে অ্যারে থেকে বেছে নেওয়া ত্রিভুজগুলির সংখ্যা খুঁজে বের করতে হবে যেগুলিকে ত্রিভুজের পার্শ্ব দৈর্ঘ্য হিসাবে নিলে ত্রিভুজ তৈরি করতে পারে। সুতরাং যদি ইনপুটটি [2,2,3,4] এর মত হয়, তাহলে ফলাফল 3 হবে কারণ তিনটি ট্রিপলেট [2,3,4] আছে প্রথম 2 ব্যবহার করে, [2,3,4] দ্বিতীয় 2 ব্যবহার করে, এবং [২,২,৩]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ret :=0, n :=সংখ্যার আকার, সংখ্যা সাজান
-
আমি n − 1 থেকে 0
সীমার মধ্যে-
ডানে :=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
