मान लीजिए हमारे पास संख्याओं की एक सरणी है, हमें सरणी से चुने गए उन ट्रिपलेट की संख्या ढूंढनी है जो त्रिभुज बना सकते हैं यदि हम उन्हें त्रिभुज की भुजा लंबाई के रूप में लें। इसलिए यदि इनपुट [2,2,3,4] जैसा है, तो परिणाम 3 होगा क्योंकि तीन ट्रिपलेट [2,3,4] पहले 2 का उपयोग करके, [2,3,4] दूसरे 2 का उपयोग करके, और [2,2,3] हैं।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
ret := 0, n := nums का आकार, nums को सॉर्ट करें
i को n-1 से 0 तक घटाते हुए
right := i-1, left := 0
जब तक left < right
sum := nums[left] + nums[right]
यदि sum > nums[i], तो ret को right-left से बढ़ाएं, right को 1 से घटाएं, अन्यथा left को 1 से बढ़ाएं
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
