দেওয়া লিস্ট nums এবং টার্গেট target। সাবসেকশন i < j < k যাতে nums[i] + nums[j] + nums[k] < target, সেই ট্রিপলেটের সংখ্যা গণনা করতে হবে।
উদাহরণ: nums=[-2,6,4,3,8], target=12 → ৫টি ট্রিপলেট: [-2,6,4], [-2,6,3], [-2,4,3], [-2,4,8], [-2,3,8]।
টু-পয়েন্টার অপ্টিমাইজেশন
- অ্যারে সর্ট করুন।
- প্রতিটি
i(০ থেকে n-3) এর জন্য:k = n-1(ডান পয়েন্টার)।- প্রতিটি
j(i+1 থেকে n-2) এর জন্য:- যখন
k > jএবংnums[i] + nums[j] + nums[k] >= target:k--। - যদি
j == k: ব্রেক। - ভ্যালিড ট্রিপলেটের সংখ্যা:
k - j(কারণj+1 ... kসব ভ্যালিড)।
- যখন
পাইথন কোড
class Solution:
def solve(self, nums, target):
nums.sort()
ans = 0
n = len(nums)
for i in range(n):
k = n - 1
for j in range(i + 1, n):
while k > j and nums[i] + nums[k] + nums[j] >= target:
k -= 1
if j == k:
break
ans += k - j
return ans
ob1 = Solution()
print(ob1.solve([-2, 6, 4, 3, 8], 12)) # 5
টাইম কমপ্লেক্সিটি: O(n²), স্পেস: O(1)। sорту করায় ইনার লুপ O(n) এ চলে।
