C++ में वैध त्रिकोण संख्या

मान लीजिए हमारे पास गैर-ऋणात्मक पूर्णांकों की एक सरणी है, हमारा कार्य सरणी से चुने गए ट्रिपलेट्स की संख्या गिनना है जो त्रिकोण बना सकते हैं यदि हम उन्हें त्रिकोण की भुजा लंबाई के रूप में लें। इसलिए यदि इनपुट [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
  • while 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; 
    } 
}; 

int main(){ 
    vector<int> v = {2,2,3,4}; 
    Solution ob; 
    cout << (ob.triangleNumber(v)); 
}

इनपुट

[2,2,3,4]

आउटपुट

3