عد مقاطع بمجموع محدد في قائمة موجبة: النافذة وتحريك حد اليسار

عدد المقاطع التي تساوي الهدف

لدينا قائمة مرتبة من أعداد صحيحة موجبة، وعدد مستهدف موجب، ونريد عدد المقاطع المتصلة غير الفارغة التي يساوي مجموعها الهدف. المقطع يمتد من موضع إلى موضع تالٍ دون تجاوز عناصر بينهما. لا نختار مجموعة قيم متفرقة، ولا نريد أكبر مجموع أو أطول مقطع تحت حد؛ نعد جميع الحدود التي تحقق المساواة المطلوبة.

تعرف مسألة CSES المسماة Subarray Sums I سؤال العد على قائمة موجبة، ويعرض دليل USACO طريقة النافذة بمؤشرين يتحركان في الاتجاه نفسه. سنطبق هذه الفكرة في مثال مؤلف، مع تسجيل حدود كل تطابق وآثار تحريك اليسار. لا ننقل مثال المصدر أو كوده، ولا نقدم النتيجة بوصفها حلًا شغلناه في منصة المسابقة أو اختبار أداء عليها.

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

تعريف مسألة العد للموجبات، مرجع النافذة وحركات المؤشرين.

سبع قيم وثلاثة مقاطع

نختار القيم اثنتين وواحدًا وثلاثًا واثنتين وواحدًا وواحدًا وأربعًا، والهدف أربعة. المواضع تبدأ من صفر إلى ستة. المقاطع المطابقة هي [1,3) التي تضم واحدًا وثلاثًا، و[3,6) التي تضم اثنتين وواحدًا وواحدًا، و[6,7) التي تضم الأربع الأخيرة وحدها. كل مجموع يساوي أربعة، لكن أطوال المقاطع اثنان وثلاثة وواحد.

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

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

ما الذي تحمله النافذة الحالية؟

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

عند انتهاء هذا التصغير، إما أن يكون المجموع أقل من الهدف، أو مساويًا له، أو تكون النافذة فارغة بعد حذف عنصر أكبر من الهدف. في حالة المساواة مع نافذة غير فارغة نسجل المقطع مرة. لا نحذف عناصر إضافية لمجرد تسجيل التطابق في النسخة التي سنراجعها؛ تصل الإضافة التالية أولًا، ثم نعيد تصغير النافذة إذا تجاوزت المجموع المطلوب.

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

لماذا توجد بداية واحدة لكل نهاية؟

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

وإذا حذفنا بداية لأن مجموعها أكبر من الهدف، فإن إبقاء تلك البداية مع إضافة قيم لاحقة موجبة سيجعل المجموع أكبر أيضًا. لا نحتاج الرجوع إليها في نهاية مستقبلية. أما البدايات التي تقع بعد الحد الذي احتفظنا به فتجعل المجموع أصغر؛ فإذا كان مجموع النافذة الحالية أقل من الهدف، لن يصل حذف المزيد من موجباتها إلى الهدف الأعلى.

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

أول تطابق بعد تصغير ستة إلى أربعة

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

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

عند إضافة الاثنتين التالية في الموضع ثلاثة، يصبح مجموع النافذة ستة مرة أخرى. نحذف الواحد عند الموضع واحد، فيبقى خمسة، ثم نحذف الثلاثة عند الموضع اثنين، فيبقى اثنان ويصير اليسار ثلاثة. لا نسجل تطابقًا في هذه النهاية؛ النافذة الباقية أقل من الهدف. وقد حذفنا فهرسين في مرحلة واحدة، دون الرجوع إلى أي فهرس حُذف سابقًا.

التطابق الأوسط والواحد الأخير

بعد المرحلة السابقة تحمل النافذة الاثنتين عند الموضع ثلاثة فقط. نضيف الواحد عند أربعة، فيصبح المجموع ثلاثة دون تطابق. ثم نضيف الواحد عند خمسة، فيصبح أربعة. نسجل [3,6)، بقيم اثنتين وواحد وواحد. طول هذا المقطع ثلاثة، وهو يختلف من طول المقطع الأول رغم أن المجموع المستهدف نفسه.

نضيف الأربع الأخيرة في الموضع ستة، فيصبح المجموع ثمانية. نطرح الاثنتين عند ثلاثة فنصل إلى ستة، ثم الواحد عند أربعة فنصل إلى خمسة، ثم الواحد عند خمسة فنصل إلى أربعة. الحد الأيسر الآن ستة، فتكون النافذة الأربع وحدها. نسجل [6,7) تطابقًا ثالثًا، ونكون قد حذفنا الفهارس من صفر إلى خمسة مرة واحدة لكل منها عبر المراحل كلها.

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

عرض الرسم بالحجم الكامل

المقاطع المتداخلة يمكن أن تعد كلها

نأخذ مثالًا آخر بأربع قيم كلها واحد، والهدف اثنان. المقاطع [0,2) و[1,3) و[2,4) تحقق الهدف، وعددها ثلاثة. يتداخل الأول والثاني في عنصر، وكذلك الثاني والثالث. هذا التداخل مسموح في سؤال العد؛ لا نطلب اختيار مجموعة مقاطع متوافقة على مورد واحد أو حذف كل عنصر بعد دخوله أول تطابق.

فإذا تخطينا إلى ما بعد المقطع الأول مباشرة بهدف منع التداخل، فسوف نغير السؤال ونفقد المقطع الأوسط. النافذة في تنفيذنا تتحرك بحسب مقارنة المجموع بالهدف، وتستمر في فحص كل نهاية. لا تستعمل التسجيل قاعدة تمنع ظهور عنصر في مقطع مطابق آخر؛ الموضع قد ينتمي إلى أكثر من مقطع، مع بقاء كل زوج حدود يُعد مرة واحدة.

هذا المثال يميز العدد من الطول الأقصى أيضًا: أكبر طول لمقطع مجموعه اثنان في هذه القائمة هو اثنان، بينما عدد هذه المقاطع ثلاثة. لا ننقل رقمًا من مسألة تعظيم طول تحت حد إلى سؤال المساواة والعد، ولو استعملت المسألتان مؤشرين متشابهين. الهدف ومعنى حالة المخرج هما اللذان يحددان ما ينبغي حفظه بعد تحريك الحدود.

الصفر يكسر تفرد البداية

نسمح مؤقتًا خارج عقد التنفيذ بثلاث قيم: صفر وصفر وأربع، والهدف أربعة. جميع المقاطع [0,3) و[1,3) و[2,3) تحقق الهدف عند النهاية نفسها. حذف صفر من البداية لا يخفض المجموع، ولذلك لم تعد حجة البداية الواحدة صحيحة. يتعين على طريقة عد تدعم الأصفار أن تتعامل مع أكثر من بداية مناسبة للنهاية ذاتها.

نسخة تجريبية تتجاهل فحص الإيجابية وتطبق قاعدة المساواة الواحدة ستحفظ واحدًا فقط لهذه النهاية، فتفقد مقطعين. نفذنا هذا المثال لنوضح حدود الحجة، ولم نقدمه بوصفه مدخلًا مقبولًا لدالتنا الخاصة بالموجبات. الدالة الصحيحة ضمن عقد المقال ترفض الصفر قبل التتبع، بدل إرجاع عدد يبدو واضحًا لكنه لا يحصي هذا المثال كاملًا.

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

السالب يغير اتجاه المجموع

نختار خارج العقد القيم ثلاثًا وسالب اثنين وثلاثًا، والهدف ثلاثة. المقطع الأول وحده يساوي ثلاثة، وكذلك العنصر الأخير وحده، فيكون العدد الصحيح اثنين. لكن حذف سالب اثنين من بداية نافذة يزيد المجموع، وإضافة قيمة سالبة قد تخفضه؛ لم تعد حركة الحدود تملك الاتجاه الذي استخدمناه مع الموجبات.

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

هذه تجربة تفسر فشل التعميم، لا توصية بحذف السالب من البيانات أو تحويله إلى موجب. قائمة بإشارات مختلفة تحتاج طريقة عد تحفظ علاقات أخرى، مثل مجاميع بوادئ مناسبة، مع تعريفها وفحوصها. في هذا المقال نلتزم القيم الصحيحة الموجبة، ونميز رفض المدخل المخالف من جواب صحيح عن مجموعة أعداد أوسع لم نعالجها.

عنصر أكبر من الهدف ونافذة فارغة

إذا كان أحد العناصر أكبر من الهدف، فقد تنكمش النافذة حتى تُحذف هذه القيمة نفسها وتصبح فارغة. مثال تسعة ثم أربعة وهدف أربعة يبدأ بالنافذة ذات التسعة، ثم يحذفها لأن مجموعها أكبر من المطلوب. يصبح اليسار بعد العنصر الأول والمجموع صفرًا، ولا نسجل مقطعًا فارغًا؛ في المرحلة التالية تضيف الأربع فتظهر المطابقة المفردة.

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

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

إعادة الترتيب تغير اتصال المقاطع

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

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

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

العدد والحدود وسجل المراحل

يقدم تنفيذ الفحص عدد المقاطع وقائمة حدودها وأثر كل مرحلة، حتى نستطيع مراجعة ما حدث. لكل حدين نجمع عناصر الأصل مباشرة، ونتأكد أن البداية أصغر من التوقف وأن المجموع يساوي الهدف. لا نساوي عدد الفهارس المحذوفة من اليسار بعدد التطابقات؛ في أصلنا حُذفت ست قيم، وسُجلت ثلاثة مقاطع فقط.

وقد نحتاج في تطبيق آخر العدد وحده، فنحذف حفظ الشواهد وأثرها لتقليل حجم المخرج. لكن ذلك لا يغير السؤال الحسابي. في نسخة المقال حفظنا التفاصيل للشرح والمراجعة، فلا نصف المساحة المستخدمة بأنها مجرد مؤشرين ومجموع دون احتساب القائمة التي أعيدت وأثر المراحل الذي خُزن. ما هو لازم للحساب يختلف من المعلومات التي قررنا إخراجها.

ولا يمثل المجموع المستهدف تلقائيًا وزنًا أو مالًا أو مدة. نستعمل أعدادًا مؤلفة على قائمة ثابتة، دون حذف قيم مفقودة أو ضبط وحدات لم تدخل المثال. إذا كانت المهمة الخارجية تجمع قياسات من أنواع مختلفة، ينبغي تحديد البيانات ومعنى الاتصال والوحدة قبل تفسير المقاطع التي تظهر. النجاح العددي هنا يثبت حدودًا ومجموعًا ضمن العقد، ولا يحسم ملاءمة استخدام آخر.

لماذا لا نعيد تمرير اليسار من البداية؟

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

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

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

مرجع يفحص جميع النطاقات مباشرة

راجعنا 3280 قائمة بأطوال من صفر إلى سبعة وقيم من واحد واثنتين وأربع. لكل قائمة جربنا أهدافًا موجبة حتى أكبر من مجموعها بوحدتين، فبلغت الأسئلة 56316. المرجع المستقل يولد كل زوج بداية وتوقف صالح ويجمع عناصره مباشرة، ثم يحتفظ بالمقاطع التي تساوي الهدف؛ لا يستعمل شرط تحريك النافذة الذي نختبره.

قارنّا الحدود نفسها والعدد، وراجعنا 371788 مرحلة تتبع من حيث المجموع بعد التصغير ومواضع الحذف وتقدم اليسار. حفظنا أمثلة التداخل والفراغ والعنصر الكبير والفرز، ونفذنا أمثلة الصفر والسالب خارج العقد لإظهار ما تفوته القاعدة. هذه فحوص محدودة، وليست برهانًا تجريبيًا لكل مدخل أو قياس سرعة أو تشغيلًا لمنصة المصادر على بياناتنا.

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