ধরুন আমাদের কাছে n পূর্ণসংখ্যার একটি অ্যারে রয়েছে যাকে nums বলা হয় এবং আমাদের একটি লক্ষ্যও রয়েছে, আমাদের এখানে সূচক ট্রিপলেটের সংখ্যা খুঁজে বের করতে হবে (i, j, k) এখানে i, j, k সবগুলি 0 থেকে n - 1 এর মধ্যে রয়েছে এবং এটি শর্ত সংখ্যা [i] + nums[j] + nums[k] <লক্ষ্য পূরণ করুন।
সুতরাং, যদি ইনপুটটি nums =[-2,0,1,3], এবং লক্ষ্য =2 এর মত হয়, তাহলে আউটপুট হবে 2, কারণ দুটি ট্রিপলেট আছে যার যোগফল 2 এর কম:[-2,0, 1] এবং [-2,0,3]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ret :=0
-
অ্যারে সাজান a
-
n :=a
এর আকার -
আরম্ভ করার জন্য i :=0, যখন i
করুন -
বাম :=i + 1, ডানে :=n - 1
-
যখন বাম <ডানে, কর −
-
যোগফল :=a[i] + a[বাম] + a[ডান]
-
যদি যোগফল
-
ret :=ret + ডান - বাম
-
(বামে 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
