ما هي تقنية المؤشرين؟

Question

IT Interview Practice · Accepted Answer

تستخدم تقنية **المؤشرين** فهرسين يتحركان عبر تسلسل لحل المشاكل في عملية واحدة — مما يحول العديد من حلول O(n²) الغاشمة إلى **O(n)**.

## الفكرة

احتفظ بمؤشرين (غالباً في النهايات، أو أحدهما بطيء والآخر سريع) وحركهما بناءً على شرط، مما يقلل العمل دون إعادة مسح.

## مثال: إيجاد زوج يجمع إلى هدف في مصفوفة مرتبة

```python
def two_sum_sorted(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo < hi:
        s = arr[lo] + arr[hi]
        if s == target:
            return (lo, hi)       # found the pair
        elif s < target:
            lo += 1               # need a bigger sum
        else:
            hi -= 1               # need a smaller sum
    return None

two_sum_sorted([1, 3, 4, 6, 9], 10)   # -> (1, 3) for 4 + 6
```

## التعقيد

- **الوقت:** O(n). **المساحة:** O(1).

## متى تستخدم / المزالق

ممتازة للمصفوفات **المرتبة**، فحوصات الأرقام المتناظرة، العكس، وإزالة التكرارات في المكان. يجب غالباً ترتيب المصفوفة لمتغير المؤشرات المتقاربة. احذر من حدود المؤشرات وشرط الحلقة (`lo < hi`).

## لماذا يهم

المؤشران الاثنان يعتبران من أعلى أنماط المقابلات الفعالة: فهي تطوي الحلقات المتداخلة في مسح خطي نظيف.

تعلمك استغلال البنية (مثل الترتيب) بدلاً من القوة الغاشمة.

الفكرة نفسها تقوم بتشغيل الدمج والتقسيم وخطوة الدمج من نوع الدمج.

الفكرة

مثال: إيجاد زوج يجمع إلى هدف في مصفوفة مرتبة

التعقيد

متى تستخدم / المزالق

لماذا يهم

أسئلة ذات صلة