ধরুন আমাদের একটি অ্যারে রয়েছে যা অ-ঋণাত্মক পূর্ণসংখ্যা নিয়ে গঠিত, আমাদের কাজ হল অ্যারে থেকে নির্বাচিত ট্রিপলেটের সংখ্যা গণনা করা যা ত্রিভুজ তৈরি করতে পারে যদি আমরা সেগুলিকে ত্রিভুজের পার্শ্ব দৈর্ঘ্য হিসাবে নিই। সুতরাং যদি ইনপুটটি [2,2,3,4] এর মত হয়, তাহলে ফলাফল হবে 3 হিসাবে [2,3,4] প্রথম 2 ব্যবহার করে, [2,3,4] দ্বিতীয় 2 ব্যবহার করে এবং [2,2] ,3]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- 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
