Longest Subarray with Sum K

+10

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

الدالة

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

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

القيود

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹
يبقى كل مجموع بادئة بين -2 × 10⁸ و2 × 10⁸، لذا تكفي الأعداد الصحيحة ذات 32 بت.
أعِد 0 عندما لا يكون هناك أي مصفوفة فرعية يكون مجموع عناصرها k.

أمثلة

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

المدخلات: nums = [4, 1, 1, 2, -1, 1]k = 3
المخرجات: 4
الشرح: [1, 1, 2, -1] عند الفهارس من 1 إلى 4 و[1, 2, -1, 1] عند الفهارس من 2 إلى 5، مجموع كل منهما 3 ويتكوّن من 4 عناصر. أنت تُرجع طولًا، لذا لا يهمّ التعادل.

سؤال إضافي

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

تلميحات

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

فُتح 0 من 3

الحل

تحوّل المجاميع التراكمية مجموع أي مصفوفة فرعية إلى عملية طرح واحدة: مجموع العناصر بعد الفهرس s وحتى الفهرس i هو prefix[i] - prefix[s]. تذكّر أول فهرس يظهر فيه كل مجموع، وستعثر عملية مرور واحدة على أطول تطابق ينتهي عند كل موضع.

وسِّع كل مصفوفة فرعية بدءًا من كل نقطة بداية

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

الفكرة

من كل نقطة بداية، امتدّ نحو اليمين وأضف كل عنصر إلى المجموع الجاري. كلما ساوى المجموع k، سجّل الطول. كل مقطع فرعي هو زوج واحد من نقطة بداية ونقطة نهاية، لذا لا يفوتك أيٌّ منها. واصل الامتداد حتى بعد تجاوز المجموع k: ابتداءً من الفهرس 2 في المثال الأول، تكون المجاميع 3 و4 و0 و2 و5، والعدد -4 هو السبب في وصول الأخير إلى 5.

هناك نحو n²/2 من الأزواج: 2 × 10^8 عملية جمع عندما n = 2 × 10^4.

الخوارزمية

اضبط best على 0.
لكل قيمة start، اضبط total على 0.
حرّك end من start إلى الفهرس الأخير، وأضف nums[end] إلى total.
عندما يساوي total القيمة k، اضبط best على الأكبر بين best وend - start + 1.
أعِد best.

def longestSubarrayWithSumK(nums, k):
    n = len(nums)
    best = 0
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            # A match may come after the total has passed k, so never stop early
            if total == k and end - start + 1 > best:
                best = end - start + 1
    return best

المجاميع التراكمية باستخدام الفهرس الأول لكل مجموع

الفكرة

يكون مجموع مقطع ينتهي عند الفهرس i مساويًا لـ k بالضبط عندما يكون أحد المجاميع السابقة مساويًا لـ prefix - k. إذا كان هناك عدة مجاميع سابقة مطابقة، فإن الأول منها يبدأ أطول مقطع، لذا تخزّن الخريطة كل مجموع عند أول ظهور له فقط. فالظهور اللاحق لا يمكنه إلا أن يبدأ مقطعًا أقصر. ابدأ الخريطة بمجموع 0 عند الفهرس -1، لكي يكون طول المقطع الذي يبدأ عند الفهرس 0 عند العثور على تطابق هو i + 1.

في المثال الأول، المجاميع هي 2، 1، 4، 5، 1، 3، 6. عند الفهرس 6، ظهر 6 - 5 = 1 لأول مرة عند الفهرس 1، ما يعطي طولًا قدره 5. يعود المجموع 1 عند الفهرس 4، والإبقاء على الفهرس 1 هو ما يتيح العثور على ذلك المقطع.

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

الخوارزمية

أنشئ خريطة first تحتوي على المجموع 0 عند الفهرس -1، واجعل prefix وbest يساويان 0.
لكل فهرس i، أضف nums[i] إلى prefix.
إذا كانت prefix - k موجودة في الخريطة عند الفهرس start، فاجعل best يساوي الأكبر من best وi - start.
إذا لم تكن prefix موجودة في الخريطة بعد، فخزّنها مع الفهرس i.
أعِد best.

def longestSubarrayWithSumK(nums, k):
    # first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
    first = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += num
        # The earliest prefix equal to prefix - k starts the longest match that ends at i
        start = first.get(prefix - k)
        if start is not None and i - start > best:
            best = i - start
        # Keep the first index only: a later one could only start a shorter subarray
        if prefix not in first:
            first[prefix] = i
    return best

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

إن استبدال الفهرس المخزَّن كلما تكرر المجموع يحفظ أحدث بداية ويعثر على تطابق أقصر. يُرجع المثال الأول 4 بدلًا من 5، لأن المجموع 1 ينتقل من الفهرس 1 إلى الفهرس 4.
النافذة التي تتقلص عندما يكون مجموعها أكبر من k تُرجع أيضًا 4 في المثال الأول. وتنتهي وهي تحتوي على [-1, 3, 1, -4, 2, 3] بمجموع 4، ولا تحذف أبدًا العنصر -1.
إن إغفال المجموع 0 عند الفهرس -1 يفوّت كل تطابق يبدأ عند الفهرس 0: فالمصفوفة [5, 0, 0, 0] مع k = 5 تُرجع 0 بدلًا من 4.
الفهرس المخزَّن هو الموضع السابق للمصفوفة الجزئية، لذا يكون طولها i - start. إن إضافة 1 تحسب عنصرًا زائدًا.

أسئلة شائعة3

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

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

لماذا تفشل تقنية النافذة المنزلقة عندما تحتوي المصفوفة على أعداد سالبة؟

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

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

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

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

اختبار #1

اختبار #2

اختبار #3

الوسائط

nums = [2, -1, 3, 1, -4, 2, 3]
k = 5

الإخراج المتوقع