পাইথনে তিনটি ইউনিক এলিমেন্ট যাদের যোগফল ঠিক k (3Sum Exact)

দেওয়া লিস্ট nums এবং টার্গেট k। তিনটি ভিন্ন এলিমেন্ট যাদের যোগফল ঠিক k হয় কিনা তা বুলিয়ান রিটার্ন করতে হবে।

উদাহরণ: nums=[11,4,6,10,5,1], k=20 → [4,6,10]=20 → True।

টু-পয়েন্টার + আর্লি টার্মিনেশন

1. অ্যারে সর্ট করুন।
2. l=0, r=n-1 (আউটারমোস্ট পয়েন্টার)।
3. যখন l < r-1:
   • t = k - nums[l] - nums[r] (মাঝপথের টার্গেট)।
   • যদি nums[r-1] < t: l++, continue (সর্বোচ্চ সম্ভাব্য যোগফলও কম)।
   • m = l+1 ... r-1 এর জন্য লুপ:
     • যদি nums[m] > t: r--, break (মাঝপথের মান বড় হয়ে গেল)।
     • যদি nums[m] == t: True রিটার্ন।
4. False রিটার্ন।

পাইথন কোড

class Solution:
    def solve(self, nums, k):
        nums.sort()
        l, r = 0, len(nums) - 1
        while l < r - 1:
            t = k - nums[l] - nums[r]
            if nums[r - 1] < t:
                l += 1
                continue
            for m in range(l + 1, r):
                if nums[m] > t:
                    r -= 1
                    break
                if nums[m] == t:
                    return True
        return False

ob1 = Solution()
print(ob1.solve([11, 4, 6, 10, 5, 1], 20))  # True

টাইম কমপ্লেক্সিটি: O(n²) ওয়ার্স্ট কেস, কিন্তু আর্লি টার্মিনেশন দিয়ে প্র্যাক্টিক্যালি ফাস্ট। স্পেস: O(1)।