Subarray Sum Equals K

+10

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

الدالة

subarraySum(nums: integer-array, k: integer) → integer

numsinteger-array: مصفوفة الأعداد الصحيحة، التي قد تحتوي على قيم سالبة وأصفار
kinteger: المجموع الذي يجب أن يصل إليه المصفوفة الفرعية ليتم احتسابها
تُرجعinteger: عدد المصفوفات الفرعية التي يساوي مجموع عناصرها k

القيود

1 ≤ nums.length ≤ 2 × 10⁴
-1000 ≤ nums[i] ≤ 1000
-10⁷ ≤ k ≤ 10⁷
يحتوي مصفوفة بهذا الطول على 200,010,000 مصفوفة فرعية كحد أقصى، لذا فإن الإجابة تتسع في عدد صحيح موقّع من 32 بت.

أمثلة

المدخلات: nums = [3, 4, -7, 1, 3, 3, 1, -4]k = 7
المخرجات: 4
الشرح: مجموع أربع سلاسل متتالية يساوي 7: [3, 4]، و[1, 3, 3]، و[3, 3, 1]، و[3, 4, -7, 1, 3, 3]. في السلسلة الأخيرة، يُلغي ‎-7 العددين 3 و4، ثم يعود المجموع إلى 7 لاحقًا، لذا قد تطابق سلسلة متتالية المطلوب حتى بعد أن يتجاوز مجموعها k.

المدخلات: nums = [1, -1, 0]k = 0
المخرجات: 3
الشرح: ثلاث مصفوفات فرعية مجموعها 0: [1, -1]، و[0]، والمصفوفة بأكملها [1, -1, 0]. مجموع التسلسل [-1, 0] هو -1، لذا لا يُحتسب.

المدخلات: nums = [2, 2, 2]k = 4
المخرجات: 2
الشرح: المتتالية [2, 2] عند الفهرسين 0 و1 والمتتالية [2, 2] عند الفهرسين 1 و2 تحتويان على القيم نفسها، لكنهما تقعان في موضعين مختلفين، لذا تُحتسب كلتاهما. مجموع المصفوفة كلها هو 6.

+17 اختبارات مخفية عند الإرسال

سؤال إضافي

كيف ستغيّر الحل لإرجاع طول أطول مصفوفة فرعية يكون مجموعها k، مع الحفاظ على زمن تنفيذ O(n)؟

تلميحات

افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.

فُتح 0 من 3

الحل

تحتوي مصفوفة من n أعداد على n(n+1)/2 مصفوفات فرعية، أي نحو 2 × 10^8 عندما يكون n = 2 × 10^4، لذا فإن جمع عناصر كل مصفوفة فرعية على حدة بطيء جدًا. كما أن القيم السالبة تستبعد استخدام النافذة المنزلقة: فقد ينخفض مجموع النافذة ثم يرتفع مجددًا، لذا لا توجد قاعدة تخبرك متى تقلّصها. تكمن الفكرة التي تحل المشكلة في كتابة مجموع كل مصفوفة فرعية على أنه الفرق بين مجموعين بادئين. ويعني عدّ المصفوفات الفرعية التي تنتهي عند العنصر الحالي ويكون مجموعها k عندئذٍ عدّ المجاميع البادئة السابقة التي تساوي المجموع البادئ الحالي ناقص k، وتجيب خريطة التجزئة عن ذلك في مرور واحد.

كل بداية مع مجموع جارٍ

صحيحة، لكنها لا تنتهي في أكبر الاختبارات

الفكرة

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

لا تحتاج إلى حلقة ثالثة لجمع عناصر كل مصفوفة فرعية. ثبّت start، ثم حرّك end خطوة واحدة إلى اليمين في كل مرة وأضف nums[end] إلى total متغير المجموع الجاري. يحتفظ المجموع دائمًا بمجموع العناصر من start إلى end، لذا تتطلب كل مصفوفة فرعية عملية جمع واحدة ومقارنة واحدة.

لا تتوقف عندما يصل المجموع إلى k أو يتجاوزه. فقد تعيده قيمة سالبة لاحقة: في المثال الأول، يتغير المجموع من الفهرس 0 إلى 3، 7، 0، 1، 4، 7، لذا يكون لهذا الموضع بداية تطابق ثانٍ عند الفهرس 5.

تعتمد الكلفة على عدد الأزواج. عندما n = 2 × 10^4، يكون عددها نحو 2 × 10^8، وهذا مناسب لـ C، لكنه بطيء جدًا بالنسبة إلى Python أو Ruby أو R.

الخوارزمية

عيّن count إلى 0.
لكل start من 0 إلى n-1، عيّن total إلى 0.
لكل end من start إلى n-1، أضف nums[end] إلى total.
إذا كان total يساوي k، فأضف 1 إلى count، وتابع في كلتا الحالتين.
أعِد count.

def subarraySum(nums, k):
    n = len(nums)
    count = 0
    for start in range(n):
        total = 0
        # Grow the subarray that begins at start, one element at a time
        for end in range(start, n):
            total += nums[end]
            if total == k:
                count += 1
    return count

المجاميع البادئة باستخدام خريطة للعدّ

الفكرة

لتكن prefix[j] مجموع أول j عناصر، مع prefix[0] = 0 للبادئة الفارغة. مجموع المصفوفة الفرعية من الفهرس i إلى الفهرس j-1 هو prefix[j] - prefix[i]. لذا يكون مجموع المصفوفة الفرعية التي تنتهي عند العنصر الحالي مساويًا لـ k بالضبط عندما يساوي مجموع بادئة سابقة مجموع البادئة الحالية ناقص k. كل بادئة سابقة كهذه تحدد بداية مصفوفة فرعية مطابقة.

مرّ على المصفوفة مرة واحدة. احتفظ بمجموع البادئة الجاري وخريطة تجزئة seen تربط كل مجموع بادئة بعدد مرات ظهوره. عند كل عنصر، أضف أولًا seen[prefix - k] إلى العدد، ثم سجّل البادئة الحالية. البحث قبل التسجيل يمنع أن تكون المصفوفة الفرعية فارغة: فعندما تكون k = 0، يؤدي التسجيل أولًا إلى مطابقة البادئة الحالية مع نفسها.

خذ المثال الأول مع k = 7. مجاميع البادئات هي 0، 3، 7، 0، 1، 4، 7، 8، 4. عندما يصل مجموع البادئة إلى 7 بعد الفهرس 1، تحتوي الخريطة على 0 واحدة، ما يعطي [3, 4]. وعندما يصل إلى 7 مرة أخرى بعد الفهرس 5، تحتوي الخريطة على قيمتي 0، البادئة الفارغة والبادئة بعد القيمة -7، ما يعطي في الوقت نفسه [3, 4, -7, 1, 3, 3] و[1, 3, 3]. وعند الوصول إلى 8 بعد الفهرس 6، تحتوي الخريطة على قيمة 1 واحدة، ما يعطي [3, 3, 1]. وبذلك يصبح المجموع 4.

إن تهيئة الخريطة بحيث يظهر 0 مرة واحدة هي ما يتيح احتساب المصفوفات الفرعية التي تبدأ عند الفهرس 0. واستخدام خريطة للعد بدلًا من مجموعة مهم لأن مجموع البادئة نفسه قد يتكرر، وكل نسخة تبدأ مصفوفة فرعية مختلفة. يحتاج كل عنصر إلى عملية بحث واحدة وتحديث واحد، لذا فالزمن هو O(n)، وتحتوي الخريطة على n+1 مفاتيح كحد أقصى.

الخوارزمية

أنشئ خريطة seen باستخدام seen[0] = 1، وعيّن prefix وcount إلى 0.
لكل عنصر، أضِفه إلى prefix.
أضِف seen[prefix - k] إلى count، واعتبر المفتاح المفقود قيمته 0.
أضِف 1 إلى seen[prefix].
أعِد count.

def subarraySum(nums, k):
    # seen[p] = how many prefixes so far add up to p; the empty prefix adds up to 0
    seen = {0: 1}
    prefix = 0
    count = 0
    for num in nums:
        prefix += num
        # Each earlier prefix equal to prefix - k starts a subarray that ends here and sums to k
        count += seen.get(prefix - k, 0)
        seen[prefix] = seen.get(prefix, 0) + 1
    return count

أخطاء شائعة وحالات حدّية

تأتي معظم الإجابات الخاطئة من التعامل مع المُدخل كما لو كانت كل قيمة موجبة، أو من تنفيذ عمليتَي الخريطة بترتيب غير صحيح.

تفشل النافذة المنزلقة التي تتقلص بمجرد أن يتجاوز المجموع k عند وجود قيم سالبة. في المثال الأول، تُرجع 2 بدلًا من 4: إذ تُبقي النافذة حدّها الأيسر عند الفهرس 0 إلى أن يتجاوز المجموع 7 عند الفهرس 6، لذا لا تحاول أبدًا [1, 3, 3] أو [3, 3, 1].
يؤدي إغفال seen[0] = 1 إلى عدم احتساب كل مقطع فرعي يبدأ عند الفهرس 0. بالنسبة إلى nums = [5] وk = 5، تُرجع 0 بدلًا من 1.
يؤدي تسجيل المجموع التراكمي الحالي قبل البحث إلى احتساب المقاطع الفرعية الفارغة عندما تكون قيمة k هي 0. بالنسبة إلى [1, -1, 0]، تُرجع 6 بدلًا من 3.
يؤدي استخدام مجموعة من المجاميع التراكمية بدلًا من خريطة للعدّ إلى نقص احتساب التكرارات. بالنسبة إلى [0, 0, 0] وk = 0، الإجابة هي 6، لأن كل نسخة سابقة من المجموع التراكمي نفسه تبدأ مقطعًا فرعيًا مختلفًا.
في أسلوب القوة الغاشمة، من الخطأ الخروج من الحلقة الداخلية عندما يتجاوز المجموع k، للسبب نفسه الذي يجعل النافذة المنزلقة غير صحيحة.

أسئلة شائعة4

ما التعقيد الزمني لمسألة مجموع المصفوفة الفرعية يساوي K؟

يعمل حل المجموع التراكمي والجدول التجزئة في زمن O(n) وباستخدام مساحة إضافية O(n): مرور واحد، مع عملية بحث وعملية تحديث لكل عنصر. يستغرق فحص كل مقطع فرعي باستخدام مجموع جارٍ زمن O(n²)، بينما يستغرق جمع عناصر كل مقطع فرعي من البداية زمن O(n³).

لماذا لا تعمل النافذة المنزلقة مع مسألة مجموع المصفوفة الجزئية الذي يساوي K؟

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

لماذا تبدأ خريطة التجزئة بربط 0 بـ 1؟

يمثل هذا الإدخال البادئة الفارغة التي تسبق العنصر الأول، ومجموعها 0. يكون مجموع المصفوفة الفرعية التي تبدأ عند الفهرس 0 مساويًا لمجموع البادئة الحالي مطروحًا منه مجموع تلك البادئة الفارغة، لذا من دون هذا الإدخال لن تُحتسب تلك المصفوفات الفرعية أبدًا. بالنسبة إلى nums = [5] وk = 5، يعثر البحث عن 5 - 5 = 0 على ذلك الإدخال ويُرجع 1.

هل يمكن حل مسألة مجموع المصفوفة الفرعية يساوي K باستخدام مساحة إضافية مقدارها O(1)؟

ليس باستخدام طريقة المرور الواحد. لعدّ المطابقات التي تنتهي عند عنصر، عليك معرفة مجاميع البادئات التي سبقته، وقد يصل عددها إلى n+1 مجموعًا مختلفًا. من دون الخريطة، ستعود إلى حساب المجموع الجاري بتعقيد O(n²). عندما تكون كل القيم موجبة، تحسب النافذة المنزلقة المصفوفات الفرعية في زمن O(n) ومساحة O(1).

Python

def subarraySum(nums, k):
    # اكتب الكود هنا

حالات الاختبار

الحالة 1

الحالة 2

الحالة 3

المدخلات

nums = [3, 4, -7, 1, 3, 3, 1, -4]
k = 7

المتوقع