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