ما هي تقنية نافذة الانزلاق؟

Question

Accepted Answer

تقنية **sliding-window** تحافظ على نطاق متجاور (نافذة) فوق مصفوفة أو سلسلة نصية وتنزلقها بدلاً من إعادة الحساب من الصفر، مما يحل العديد من مسائل المصفوفة الجزئية/السلسلة الجزئية في **O(n)**.

## الفكرة الأساسية

قم بتوسيع النافذة بتحريك الحافة اليمنى؛ قم بتقليصها بتحريك الحافة اليسرى عند انتهاك قيد ما. أعد استخدام الحساب السابق بدلاً من إعادة المسح.

## مثال: أقصى مجموع لأي نافذة بحجم k

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # sum of first window
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # add new, drop old
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## التعقيد الزمني والمكاني

- **الوقت:** O(n) — يدخل كل عنصر ويغادر النافذة مرة واحدة فقط.
- **المساحة:** O(1) للنوافذ الثابتة، O(k) عند تتبع المحتويات.

## متى يتم الاستخدام / الأخطاء الشائعة

استخدم لحل مسائل "أطول/أقصر/أقصى مصفوفة جزئية بخاصية X". للنوافذ **المتغيرة**، قم بتقدم المؤشر الأيسر لاستعادة القيد. احذر من أخطاء off-by-one عند إضافة/إزالة العناصر الحدودية.

## لماذا هذا مهم

تزيل نافذة الانزلاق العمل الزائد، وتحول إعادة الحساب O(n·k) إلى مرور واحد.

هي النمط الأساسي لمسائل السلسلة النصية والمصفوفة الجزئية التي تظهر باستمرار في المقابلات.

الرؤية — إعادة استخدام النتيجة السابقة بدلاً من إعادة الحساب — تعممت على البث والبيانات في الوقت الفعلي.