পাইথনে সর্টেড লিস্টে দুটি নম্বরের যোগফল k হয় কিনা চেক করা (O(1) স্পেস)

একটি এসেন্ডিং অর্ডারে সর্টেড লিস্ট nums এবং টার্গেট k দেওয়া আছে। যেকোনো দুটি নম্বরের যোগফল k হয় কিনা চেক করুন (নেগেটিভ নম্বরও থাকতে পারে)। কনস্ট্যান্ট স্পেস ব্যবহার করুন।

ইনপুট উদাহরণ

nums = [-8, -3, 2, 7, 9]
k = 4

আউটপুট: True (7 + (-3) = 4)

অ্যালগরিদম (Two Pointers)

1. i = 0 (শুরু), j = len-1 (শেষ)।
2. cur_sum = nums[i] + nums[j]।
3. cur_sum == k → True।
4. cur_sum < k → i++ (বড় সংখ্যা লাগবে)।
5. cur_sum > k → j-- (ছোট সংখ্যা লাগবে)।

পাইথন কোড

def solve(nums, k):
    i = 0
    j = len(nums) - 1
    while i < j:
        cur_sum = nums[i] + nums[j]
        if cur_sum == k:
            return True
        elif cur_sum < k:
            i += 1
        else:
            j -= 1
    return False

# টেস্ট
print(solve([-8, -3, 2, 7, 9], 4))  # True

ব্যাখ্যা

সর্টেড অ্যারেতে টু-পয়েন্টার টেকনিক। সময় জটিলতা O(n), স্পেস O(1)। হ্যাশম্যাপ ব্যবহার না করে স্পেস বচত।