نافذة متغيرة بمؤشرين

لا تثبّت بعض المسائل طول النافذة. بل تكبر النافذة وتصغر للحفاظ على تحقق شرط معين، مثل بقاء المجموع دون حد معين.

احتفظوا بفهرسين، هما left وright، لتحديد حافتي النافذة. يوسّع المؤشر right النافذة، بينما يتبعه left لتصغيرها عند الحاجة.

تحرّكوا عبر كل عنصر باتجاه اليمين وأدرجوه في النافذة. وحدّثوا حالتها الجارية، مثل إضافة القيمة الجديدة إلى مجموع.

ما دامت النافذة تنتهك القاعدة، حرّكوا left إلى اليمين وأزيلوا ذلك العنصر. وبذلك يعود الشرط إلى التحقق دون الرجوع إلى الخلف.

عند انتهاء الحلقة الداخلية، تكون النافذة من left إلى right صالحة. ويكون طولها right ناقص left زائد واحد، وهي جاهزة للاستخدام.

حدّثوا إجابتكم باستخدام هذه النافذة الصالحة، وغالبًا ما تكون الأطول التي ظهرت حتى الآن. نفّذوا ذلك في كل تكرار حتى لا تفوتكم أي نافذة.

يتحرك كل مؤشر إلى الأمام فقط ولا يعود إلى الخلف. ويتقدم left وright معًا بحد أقصى n خطوة، لذلك تكون عملية المرور كاملة بتعقيد O(n).

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

للحصول على أقصر نافذة صالحة، صغّروا النافذة ما دام الشرط متحققًا وسجّلوا النتيجة قبل التوقف. وتبقى آلية المؤشرين نفسها.

إذا كان التصغير قد يفرغ النافذة، فتحققوا من تجاوز left لـ right. وتأكدوا أيضًا من العثور على إجابة فعلية قبل إعادتها.

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

تطبقون نافذة متغيرة بمؤشرين على مصفوفة حجمها n.

وسّعوا right لإدراج العناصر، وصغّروا left عند خرق القاعدة، وسجّلوا كل نافذة صالحة. وتحافظ المؤشرات التي تتحرك إلى الأمام فقط على التعقيد O(n). ✅