بتل کد Battle Codeدارد باز می‌شود…

جواب «Two Pointers» چالش 12 از جلسه‌ی 31

سؤال

خط اول یک لیست مرتب صعودی از اعداد صحیح و خط دوم عدد target. با دو اشاره‌گر left = 0 و right = n - 1 این الگوریتم را اجرا کنید: تا وقتی left < right، یک گام بشمارید؛ اگر جمع برابر target بود متوقف شوید، اگر کمتر بود left و اگر بیشتر بود right را حرکت دهید. چاپ کنید <a> + <b> = <target> یا none، و سپس steps=<تعداد گام‌ها>.

راهنما

این روش O(n) است، در برابر O(n²) جست‌وجوی همه‌ی جفت‌ها، و فقط روی داده‌ی مرتب درست کار می‌کند.

یک جواب درست

nums = list(map(int, input().split()))
target = int(input())
left, right = 0, len(nums) - 1
steps = 0
found = None
while left < right:
    steps += 1
    s = nums[left] + nums[right]
    if s == target:
        found = (nums[left], nums[right])
        break
    if s < target:
        left += 1
    else:
        right -= 1
print(f"{found[0]} + {found[1]} = {target}" if found else "none")
print(f"steps={steps}")

اول خودت امتحان کن؛ جواب‌های دیگر هم قبول است. برگرد و خودت حلش کن