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.

שאלת המשך

איך היית משנה את הפתרון כדי להחזיר את האורך של תת-המערך הארוך ביותר שסכומו 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, ולכן לאותו start יש התאמה שנייה באינדקס 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, המפה מכילה שני אפסים, הקידומת הריקה והקידומת שאחרי ה--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 היא שגויה מאותה סיבה כמו בחלון ההזזה.

שאלות נפוצות3

מהי סיבוכיות הזמן של Subarray Sum Equals K?

פתרון סכום הקידומות ומפת הגיבוב פועל בזמן O(n) ובצורך ב־O(n) מקום נוסף: מעבר אחד, עם חיפוש אחד ועדכון אחד לכל איבר. בדיקת כל תת־מערך באמצעות סכום מצטבר אורכת O(n²), וחיבור כל תת־מערך מחדש מההתחלה אורכת O(n³).

למה חלון הזזה לא עובד עבור Subarray Sum Equals K?

חלון הזזה מסתמך על כך שהסכום גדל כשהחלון מתרחב וקטן כשהוא מצטמצם, והדבר נכון רק כאשר כל הערכים חיוביים. כשיש ערכים שליליים, חלון שסכומו כבר גדול מדי עדיין יכול להפוך להתאמה אחרי שהוא גדל עוד, ולכן אין כלל שמורה לך מתי להזיז את הקצה השמאלי. אם כל הערכים היו חיוביים, חלון הזזה היה פותר זאת בזמן O(n) ובמקום O(1).

למה מפת הגיבוב מתחילה בכך ש־0 ממופה ל־1?

הרשומה הזאת מייצגת את הקידומת הריקה שלפני האיבר הראשון, שסכומה הוא 0. סכום של תת־מערך שמתחיל באינדקס 0 הוא סכום הקידומת הנוכחי פחות הקידומת הריקה הזאת, ולכן בלי הרשומה הזאת תת־המערכים האלה לעולם לא ייספרו. עבור nums = [5] ו־k = 5, החיפוש של 5 - 5 = 0 מוצא את הרשומה הזאת ומחזיר 1.

def subarraySum(nums, k):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

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

הפלט הצפוי