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