الگوی دو اشاره‌گر (Two Pointers)

ایده الگو

دو اشاره‌گر (Two Pointers) دو اندیس (معمولاً از دو سر) روی داده حرکت می‌دهند و جستجوی O(n²) را به O(n) تبدیل می‌کنند. شرط طلایی: داده مرتب باشد (یا مرتب‌کردن منطقی باشد).

چرا جواب می‌دهد؟

در آرایه مرتب با اشاره‌گر چپ و راست:

• جمع کمتر از هدف ← فقط چپ جلو برود (راست را کم کن؟ نه! جمع کمتر می‌شود)
• جمع بیشتر ← فقط راست عقب بیاید

هر گام، دست‌کم یک عنصر را «قطعاً جواب نیست» حذف می‌کند — پس حداکثر n گام!

سه شکل رایج

مسائل کلاسیک

• Two Sum در آرایه مرتب: جفت با جمع هدف
• معکوس‌سازی آرایه درجا: چپ و راست جابه‌جا، به هم برسند
• حذف تکراری‌ها: اشاره‌گر کند (آخرِ بخش یکتا) و تند (اسکن)
• سه‌تایی با جمع صفر: یک عنصر ثابت + Two Sum روی بقیه!
• ظرف با بیشترین آب: حرکت از عریض‌ترین، جلو رفتن از کوتاه‌تر

الگوی کد

left, right = 0, len(arr) - 1
while left < right:
    if شرط_برقرار(arr[left], arr[right]):
        # جواب پیدا شد یا ثبت کن
        ...
    elif نیاز_بزرگتر:
        left += 1
    else:
        right -= 1

جمع‌بندی

• دو اشاره‌گر از دو سر + داده مرتب = O(n)
• هر گام یک گزینه را قطعاً حذف می‌کند
• سه‌تایی = حلقه + Two Sum داخلی: O(n²)
• نشانه: «آرایه مرتب + جفت/سه‌تایی با شرط»