ধরুন আমাদের একটি অ্যারে আছে যা অঋণাত্মক পূর্ণসংখ্যা নিয়ে গঠিত, আমাদের কাজ হল অ্যারে থেকে নির্বাচিত ত্রিকগুলির সংখ্যা গণনা করা যাতে সেগুলি ত্রিভুজের পাশের দৈর্ঘ্য হিসেবে নেওয়া যায় ত্রিভুজ তৈরি করতে। তাই যদি ইনপুট হয় [2,2,3,4], তবে ফলাফল হবে ৩ কারণ [2,3,4] প্রথম ২ ব্যবহার করে, [2,3,4] দ্বিতীয় ২ ব্যবহার করে, এবং [2,2,3]।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- ret := ০, n := nums-এর আকার, nums সাজান
- i = n – ১ থেকে ০ পর্যন্ত নিচের দিকে
- right := i – ১, left := ০
- যখন left < right
- sum := nums[left] + nums[right]
- যদি sum > nums[i], তবে ret right – left দ্বারা বৃদ্ধি করুন, right ১ হ্রাস করুন, অন্যথায় left ১ বৃদ্ধি করুন
- ret ফেরত দিন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন −
উদাহরণ
#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
