मान लीजिए कि हमारे पास n पूर्णांकों की एक सरणी है जिसे अंक कहा जाता है और हमारे पास एक लक्ष्य भी है, हमें इंडेक्स ट्रिपलेट्स (i, j, k) की संख्या ज्ञात करनी है, यहां i, j, k सभी 0 से n - 1 की सीमा में हैं और वह शर्तों को पूरा करें nums[i] + nums[j] + nums[k] <लक्ष्य।
इसलिए, यदि इनपुट संख्या =[-2,0,1,3], और लक्ष्य =2 की तरह है, तो आउटपुट 2 होगा, क्योंकि दो ट्रिपल हैं जो योग 2 से कम हैं:[-2,0, 1] और [-2,0,3].
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
रिट:=0
-
सरणी को क्रमबद्ध करें a
-
n :=आकार का
-
इनिशियलाइज़ i :=0 के लिए, जब i
-
बाएँ:=i + 1, दाएँ:=n - 1
-
जबकि बाएँ <दाएँ, करें -
-
योग :=a[i] + a[बाएं] + a[दाएं]
-
अगर योग <टी, तो -
-
रिट :=रिट + राइट - लेफ्ट
-
(बाएं 1 से बढ़ाएं)
-
-
अन्यथा
-
(दाएं 1 से घटाएं)
-
-
-
-
वापसी रिट
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
#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;
}
};
main(){
Solution ob;
vector<int< v = {-2,0,1,3};
cout << (ob.threeSumSmaller(v,2));
} इनपुट
[-2,0,1,3] 2
आउटपुट
2