🚀 حل سوال "Two Sum II - Input Array Is Sorted" از LeetCode با تحلیل کامل! 🔍

یک آرایه مرتب‌شده از اعداد به شما داده می‌شود (بر اساس صعودی) و یک عدد هدف (target). شما باید دو عدد پیدا کنید که جمع آنها برابر target شود.

• فرض کنید دقیقاً یک جواب وجود دارد.

• باید ایندکس دو عدد را برگردانید (ایندکس‌ها از ۱ شروع می‌شوند، نه ۰).

مثال:

ورودی:

numbers = [2, 7, 11, 15], target = 9

خروجی:

[1, 2]

توضیح: چون numbers[1] + numbers[2] = 2 + 7 = 9.

راه‌حل (با استفاده از دو پوینتر):

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]  # چون ایندکس‌ها از ۱ شروع می‌شوند
        elif current_sum < target:
            left += 1
        else:
            right -= 1
    return [-1, -1]  # در صورت عدم وجود جواب (طبق صورت مسئله، این خط اجرا نمی‌شود)

توضیح راه‌حل:

1. از دو پوینتر استفاده می‌کنیم: یکی در ابتدا (left) و دیگری در انتهای آرایه (right).

2. جمع دو عدد در این پوینترها را محاسبه می‌کنیم:

   • اگر جمع برابر target بود، جواب را برمی‌گردانیم.

   • اگر جمع کمتر از target بود، پوینتر چپ را یک واحد افزایش می‌دهیم (چون آرایه مرتب است و باید عدد بزرگتری انتخاب کنیم).

   • اگر جمع بیشتر از target بود، پوینتر راست را کاهش می‌دهیم.

3. این کار را تا زمانی که دو پوینتر به هم برسند ادامه می‌دهیم.

پیچیدگی زمانی:

• O(n) چون در بدترین حالت تمام عناصر آرایه یک بار پیمایش می‌شوند.

• O(1) از نظر حافظه، چون فقط از دو متغیر استفاده شده.