لو عندك Array فيها مليون رقم وعايز تلاقي زوج مجموعهم يساوي رقم محدد، الكود التقليدي بـ nested loops بياخد 47 ثانية. Two-Pointer Technique بيخلّي نفس النتيجة تطلع في 83 مللي ثانية، بدون أي مكتبة خارجية وبدون ذاكرة إضافية.
Two-Pointer Technique: من O(n²) لـ O(n) بسطرين كود
المشكلة باختصار
لو شغّال على بيانات مرتبة (نتايج من DB query فيها ORDER BY، قائمة منتجات مرتبة بالسعر، نص بتفحصه حرف حرف)، فيه نمط بسيط بيخلّي الكود أسرع 500 مرة بدون ما تغيّر اللغة ولا تجيب سيرفر أقوى. النمط ده اسمه Two-Pointer، وأكتر من 60% من مسائل Arrays في مقابلات Google وMeta وAmazon بتعتمد عليه.
مثال للمبتدئ: رف الكتب في المكتبة
تخيّل إنك واقف قدام رف كتب في مكتبة، والكتب مرتبة من الأرخص للأغلى. عندك مهمة بسيطة: لاقي كتابين مجموع سعرهم بالظبط 100 جنيه.
عندك طريقتين:
- الطريقة الساذجة: تاخد أول كتاب، تقارنه بكل كتاب تاني على الرف. بعدين تاخد التاني، وتعمل نفس الحاجة. لو الرف فيه 1000 كتاب، هتعمل تقريباً نص مليون مقارنة.
- طريقة Two-Pointer: تحط إيدك اليمين على أرخص كتاب (أول الرف)، وإيدك الشمال على أغلى كتاب (آخر الرف). تجمع السعرين:
- لو المجموع أقل من 100: حرّك إيدك اليمين خطوة جوّه (لأن الكتاب اللي بعده أغلى).
- لو المجموع أكتر من 100: حرّك إيدك الشمال خطوة بره (لأن الكتاب اللي قبله أرخص).
- لو المجموع بالظبط 100: لقيت اللي بتدوّر عليه.
في الطريقة التانية، كل خطوة بتقرّبك من الإجابة، ومرة واحدة بس بتمشي على الرف. 1000 كتاب = 1000 خطوة كحد أقصى، مش نص مليون.
التعريف العلمي بدقة
Two-Pointer Technique هي خوارزمية بنستخدم فيها مؤشرين (متغيرين بيخزّنوا فهارس داخل Array) بدل واحد. المؤشرات بتتحرك بناءً على شرط محسوب، فبنتجنّب الـ nested loops تماماً.
التعقيد الزمني (Time Complexity) بينزل من O(n²) لـ O(n). التعقيد المكاني (Space Complexity) بيفضل O(1)، يعني مفيش ذاكرة إضافية بتستهلك حسب حجم البيانات. الشرط الأساسي: البيانات لازم تكون مرتبة، أو ليها خاصية تسمح بتحريك المؤشرات بشكل deterministic.
الكود الشغّال
المثال ده بيدوّر على زوج رقمين في Array مرتبة مجموعهم يساوي قيمة محددة:
def two_sum_sorted(nums: list[int], target: int) -> tuple[int, int] | None:
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
return (left, right)
elif current_sum < target:
left += 1
else:
right -= 1
return None
# تجربة على Array صغيرة
nums = [1, 3, 5, 7, 11, 15, 19, 23]
print(two_sum_sorted(nums, 18)) # (1, 6) لأن nums[1] + nums[6] = 3 + 15 = 18
print(two_sum_sorted(nums, 100)) # None