Two Pointers

تقنية المؤشّرين Two Pointers

تقنية المؤشّرين تستخدم مؤشّرين يتحرّكان عبر مصفوفة (غالبًا مرتّبة) لحلّ مسائل بتعقيد O(n) بدل الحل الساذج O(n²) بحلقتين متداخلتين.

بدل مقارنة كل زوج ممكن من العناصر (O(n²))، يتحرّك مؤشّران — عادة من الطرفين نحو المنتصف، أو أحدهما يتقدّم أسرع من الآخر — بحيث يُستبعد جزء من الاحتمالات بكل خطوة اعتمادًا على مقارنة بسيطة. تعتمد الفعالية غالبًا على كون البيانات مرتّبة سلفًا.

الصياغة

left, right = 0, len(arr) - 1
while left < right:
    # قارن أو اجمع arr[left] و arr[right]
    # حرّك left أو right حسب النتيجة

📄 مثال

def has_pair_with_sum(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            return True
        elif current_sum < target:
            left += 1   # نحتاج مجموعًا أكبر
        else:
            right -= 1  # نحتاج مجموعًا أصغر
    return False

sorted_arr = [1, 2, 4, 7, 11, 15]
print(has_pair_with_sum(sorted_arr, 15))  # True (4 + 11)

أهم النقاط

النقطة	الوظيفة
التعقيد الزمني	O(n) عادةً — بدل O(n²) بالحل الساذج بحلقتين متداخلتين
التعقيد المكاني	O(1) — لا يحتاج ذاكرة إضافية عادةً
الشرط الشائع	غالبًا تحتاج بيانات مرتّبة مسبقًا لتعمل بمنطقها الأساسي (كمثال إيجاد زوج بمجموع معيّن)

💡 نصائح عملية

أي مسألة على مصفوفة مرتّبة تسأل عن 'زوج' أو 'ثلاثي' بشرط معيّن (مجموع، فرق) — جرّب المؤشّرين قبل أي حل آخر

⚠️ أخطاء شائعة

تطبيقها على بيانات غير مرتّبة بمنطق يفترض الترتيب (كإيجاد زوج بمجموع معيّن) — يُعطي نتائج خاطئة، رتّب البيانات أولًا إن لزم

🎓 تريد فهم الصورة الكاملة خطوة بخطوة؟ ابدأ من مسار DSA الكامل بالعربي.