سوال 167

عنوان سوال : Two Sum II - Input Array Is Sorted

• متوسط
• جستجو باینری
• دو اشاره گر
• آرایه

---

یک آرایهٔ ۱-ایندکسی از اعداد صحیح به نام numbers داده شده است که از قبل به‌صورت صعودی (non-decreasing) مرتب شده است.
هدف این است که دو عدد پیدا کنیم که مجموعشان برابر با مقدار target باشد.
این دو عدد باید numbers[index1] و numbers[index2] باشند، به‌طوری که:

• 1 <= index1 < index2 <= numbers.length
• فقط یک جواب معتبر وجود دارد.
• اجازه ندارید از یک عنصر بیش از یک‌بار استفاده کنید.
• الگوریتم باید تنها از فضای کمکی ثابت (O(1)) استفاده کند.

در نهایت باید اندیس‌ها را با یک واحد اضافه به‌صورت [index1, index2] برگردانید.

---

مثال:

ورودی:
numbers = [2,7,11,15]
target = 9

خروجی:
[1,2]

توضیح:
2 + 7 = 9
پس اندیس‌ها (با احتساب ۱-ایندکس بودن): [1, 2]

---

محدودیت‌ها:

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• آرایه به‌صورت صعودی مرتب شده است.
• -1000 <= target <= 1000
• دقیقاً یک پاسخ معتبر وجود دارد.

راه حل

public int[] TwoSum(int[] numbers, int target)
{
    var left = 0;
    var right = numbers.Length - 1;

    while (left < right)
    {
        var sum = numbers[left] + numbers[right];

        if (sum > target)
        {
            right -= 1;
        }
        else if (sum < target)
        {
            left += 1;
        }
        else
        {
            return [left + 1, right + 1];
        }
    }

    return [];
}