عدّ المصفوفات الفرعية ذات المجموع المستهدف

إليك التحدي الآن: احسب عدد المصفوفات الفرعية التي يساوي مجموعها قيمة مستهدفة k. إن فحصت كل زوج فسيكون ذلك بطيئًا، لكن المجاميع التراكمية مع خريطة تجزئة تحل المسألة. 🎯

يساوي مجموع المصفوفة الفرعية prefix[r + 1] ناقص prefix[l]. لذا يعني أن يكون المجموع k أن تختلف قيمتا مجموع تراكمي بمقدار k بالضبط.

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

بدلًا من الرجوع والفحص في كل مرة، تذكّر عدد مرات ظهور كل قيمة من قيم المجموع التراكمي. يجيبك العدّاد المتراكم في O(1).

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

قبل الحلقة، سجّل أن المجموع التراكمي 0 ظهر مرة واحدة. تتيح هذه التهيئة احتساب المصفوفات الفرعية التي تبدأ عند الفهرس 0.

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

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

ينفّذ كل عنصر عملًا بزمن ثابت، لذا يُحسب العدد كله في O(n). وهذا يتفوق على الحل بالقوة الغاشمة ذي الزمن O(n تربيع) عند التعامل مع مدخلات كبيرة.

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

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

مجموعك التراكمي الجاري هو P والقيمة المستهدفة هي k.

يمكنك حساب عدد المصفوفات الفرعية ذات المجموع المستهدف في O(n) باستخدام المجاميع التراكمية وخريطة التكرارات. هيّئ المجموع التراكمي 0، ثم احسب العدد قبل التسجيل. ✅