পাইথনে তিনটি ইউনিক এলিমেন্ট যাদের যোগফল k-র সবচেয়ে কাছাকাছি (3Sum Closest)

দেওয়া লিস্ট nums এবং টার্গেট k। তিনটি ভিন্ন এলিমেন্ট (a,b,c) খুঁজতে হবে যাতে |a+b+c - k| ন্যূনতম হয়। আউটপুট হবে সেই ন্যূনতম এবসোলিউট ডিফারেন্স।

উদাহরণ: nums=[2,5,25,6], k=14 → [2,5,6]=13 → ডিফারেন্স |13-14|=1।

টু-পয়েন্টার অ্যাপ্রোচ (সর্টেড অ্যারে)

1. অ্যারে সর্ট করুন।
2. প্রতিটি i (০ থেকে n-3) এর জন্য:
   • j = i+1, k = n-1।
   • যখন j < k:
     • s = nums[i] + nums[j] + nums[k]
     • যদি s <= target: ans = min(ans, target-s), j++।
     • অন্যথায়: ans = min(ans, s-target), k--।
3. ans রিটার্ন।

পাইথন কোড

class Solution:
    def solve(self, nums, target):
        nums.sort()
        ans = 1e9
        for i in range(len(nums)):
            j = i + 1
            k = len(nums) - 1
            while j < k:
                s = nums[i] + nums[j] + nums[k]
                if s <= target:
                    ans = min(ans, target - s)
                    j += 1
                else:
                    ans = min(ans, s - target)
                    k -= 1
        return ans

ob1 = Solution()
print(ob1.solve([2, 5, 25, 6], 14))  # 1

টাইম কমপ্লেক্সিটি: O(n²), স্পেস: O(1) (সর্টিং বাদ দিয়ে)। এটি ক্লাসিক 3Sum Closest সমস্যা।