C++-এ 3Sum Smaller: টার্গেট থেকে ছোট তিনটি সংখ্যার যোগফলের ট্রিপলেট গণনা

একটি ইন্টিজার অ্যারে nums এবং একটি টার্গেট target দেওয়া আছে। ইনডেক্স ট্রিপলেট (i, j, k) (এখানে i < j < k) এর সংখ্যা বের করতে হবে যাতে nums[i] + nums[j] + nums[k] < target।

উদাহরণ

ইনপুট: nums = [-2,0,1,3], target = 2

আউটপুট: 2

বৈধ ট্রিপলেটগুলো: [-2,0,1] (সাম = -1) এবং [-2,0,3] (সাম = 1)।

সমাধানের পদ্ধতি (Sort + Two Pointers)

1. অ্যারে সর্ট করুন।
2. ret = 0।
3. i = 0 থেকে n-3 পর্যন্ত লুপ:
   • left = i+1, right = n-1।
   • while (left < right):
     • sum = a[i] + a[left] + a[right]।
     • যদি sum < target: বাম থেকে ডান পর্যন্ত সবই বৈধ (কারণ সর্টেড) → ret += right - left, left++।
     • অন্যথায়: right--।
4. 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