C++ में 3Sum Smaller - लक्ष्य से कम त्रिक गिनें

समस्या विवरण

मान लीजिए हमारे पास n पूर्णांकों की सरणी nums है और एक लक्ष्य है, हमें सूचकांक त्रिक (i, j, k) की संख्या ढूंढनी है जहां i, j, k सभी 0 से n-1 की सीमा में हैं और nums[i] + nums[j] + nums[k] < लक्ष्य को संतुष्ट करते हैं।

उदाहरण के लिए, यदि nums = [-2,0,1,3] और लक्ष्य = 2 है, तो आउटपुट 2 होगा, क्योंकि दो त्रिक हैं जिनका योग 2 से कम है: [-2,0,1] और [-2,0,3]।

समाधान दृष्टिकोण

सॉर्टिंग + दो पॉइंटर तकनीक O(n^2) समय में:

1. ret := 0
2. सरणी a को सॉर्ट करें
3. n := a का आकार
4. i को 0 से n-3 तक लूप करें:
   • left := i + 1, right := n - 1
   • जब left < right:
     • sum := a[i] + a[left] + a[right]
     • यदि sum < लक्ष्य:
       • ret += right - left (बाएं और दाएं के बीच सभी वैध हैं)
       • left++
     • अन्यथा right--
5. ret लौटाएं

C++ कार्यान्वयन

#include <bits/stdc++.h> 
using namespace std; 

class Solution { 
public: 
    int threeSumSmaller(vector<int>& a, int t) { 
        int ret = 0; 
        sort(a.begin(), a.end()); 
        int n = a.size(); 
        for (int i = 0; i < n - 2; i++) { 
            int left = i + 1; 
            int right = n - 1; 
            while (left < right) { 
                int sum = a[i] + a[left] + a[right]; 
                if (sum < t) { 
                    ret += right - left; 
                    left++; 
                } 
                else 
                    right--; 
            } 
        } 
        return ret; 
    } 
}; 

int main(){ 
    Solution ob; 
    vector<int> v = {-2,0,1,3}; 
    cout << (ob.threeSumSmaller(v,2)); 
    return 0;
}

इनपुट

[-2,0,1,3] 2

आउटपुट

2