كيف تحول تقنيتا المؤشرين (Two Pointers) والنافذة المنزلقة (Sliding Window) المسائل التربيعية O(N^2) إلى خطية O(N)؟

الإجابة المختصرة

عبر الاحتفاظ بمؤشرين يتحركان في اتجاه محدد بدلاً من فحص كل الأزواج الممكنة بحلقتين متداخلتين، مما يضمن زيارة كل عنصر عدداً ثابتاً من المرات.

الشرح

في تقنية Two Pointers (مثل مسألة Two Sum على مصفوفة مرتبة)، نضع مؤشراً في البداية والآخر في النهاية، فإذا كان المجموع صغيراً نحرك الأيسر للأمام، وإذا كان كبيراً نحرك الأيمن للخلف بزمن O(N). وفي Sliding Window (مثل إيجاد أطول سلسلة فرعية بدون تكرار)، نوسع النافذة بزيادة المؤشر الأيمن، وعند اختراق الشرط نقوم بتقليصها بزيادة المؤشر الأيسر، محافظين على فحص النطاق المتحرك بزمن خطي ثابت.

مثال بالكود

let left = 0;
for (let right = 0; right < s.length; right++) {
  // توسيع النافذة
  while (windowConditionBroken()) {
    // تقليص النافذة من اليسار
    left++;
  }
  maxLength = Math.max(maxLength, right - left + 1);
}

أخطاء شائعة

• محاولة استخدام Two Pointers على مصفوفة غير مرتبة لمسائل الأرقام، مما يقود لقرارات توجيه خاطئة.

أسئلة متابعة

• ما هي أهم حيل معالجة البتات (Bit Manipulation) مثل فحص القوى الثنائية وحساب عدد البتات وإيجاد العنصر الفريد عبر XOR؟

المصادر

• CP-Algorithms — Minimum Stack / Minimum Queue (sliding window)