Running Sum of an Array

Q: מהו הסכום המצטבר של מערך?

זהו מערך שני שבו כל איבר הוא הסכום של כל הערכים עד למיקום הזה, כולל, במערך הראשון. הוא נקרא גם סכום קידומות או סכום מצטבר. הסכום הרץ של [3, 1, 4, 1, 5] הוא [3, 4, 8, 9, 14] .

Q: מהי סיבוכיות הזמן של חישוב סכום מצטבר?

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

Q: האם אפשר לחשב את הסכום המצטבר במקום?

כן. עוברים מאינדקס 1 עד הסוף ומגדירים nums[i] += nums[i-1] . עד אז nums[i-1] כבר מכיל את הסכום של כל הערכים עד אליו, ולכן כל איבר מסתיים כסכום הקידומות שלו. הערכים המקוריים הולכים לאיבוד.

Q: איך סכומי קידומות עוזרים בשאילתות סכום לטווח?

הסכום של פרוסה nums[l..r] הוא prefix[r] - prefix[l-1] , או prefix[r] כאשר l = 0 . עם [3, 4, 8, 9, 14] , האינדקסים 2 עד 4 מסתכמים ב־ 14 - 4 = 10 . כל שאילתה אורכת O(1) לאחר מעבר אחד של O(n) .

מתחיליםסכומי תחיליות

+10

נתון לך מערך של מספרים שלמים nums. החזר מערך חדש באותו אורך, שהאיבר שלו באינדקס i הוא nums[0] + nums[1] + ... + nums[i], כלומר הסכום של i+1 המספרים הראשונים.

פונקציה

runningSum(nums: integer-array) → integer-array

numsinteger-array: המספרים שיש לחבר משמאל לימין
מחזירהinteger-array: הסכומים המצטברים, אחד לכל איבר ב־nums

אילוצים

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
כל הסכומים המצטברים מתאימים למספר שלם חתום בן 32 סיביות.

דוגמאות

קלט: nums = [3, 1, 4, 1, 5]
פלט: [3, 4, 8, 9, 14]
הסבר: המשיכו להוסיף: 3, אחר כך 3 + 1 = 4, 4 + 4 = 8, 8 + 1 = 9 ו־9 + 5 = 14. כל סכום עובר לאינדקס של המספר שנוסף אחרון.

קלט: nums = [-2, 5, -3]
פלט: [-2, 3, 0]
הסבר: מספרים שליליים מורידים את הסכום: -2, ואז -2 + 5 = 3, ואז 3 + (-3) = 0.

קלט: nums = [7]
פלט: [7]
הסבר: למספר יחיד יש סכום מצטבר אחד, הוא עצמו, ולכן התשובה היא [7].

שאלת המשך

האם תוכל לבנות את אותו הדבר עבור רשת, שבה כל תא מכיל את הסכום של המלבן מהפינה השמאלית העליונה ועד לאותו תא?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

כל תשובה היא הסכום של קידומת של nums, וקידומות סמוכות נבדלות באיבר אחד. חישוב מחדש של כל קידומת מההתחלה חוזר על כמעט כל העבודה. במקום זאת, העבירו סכום אחד קדימה, וכך כל תשובה דורשת פעולת חיבור אחת בלבד.

חבר מחדש כל קידומת מההתחלה

האינטואיציה

פעלו לפי ההגדרה: עבור כל אינדקס i, התחילו עם סכום כולל של 0, הוסיפו את nums[0] עד nums[i], ושמרו אותו. זה נכון משום שכל תשובה מחושבת בדיוק כפי שהוגדרה.

האינדקס i דורש i+1 פעולות חיבור, ולכן המערך דורש n(n+1)/2: כ־1.25 × 10^7 פעולות חיבור עבור n = 5000, כאשר 5000 יספיק.

אלגוריתם

צרו מערך תשובות באורך n.
עבור כל אינדקס i, הגדירו total = 0.
הוסיפו את nums[j] ל־total עבור כל j מ־0 עד i.
שמרו את total באינדקס i של התשובות, והחזירו את התשובות לאחר האינדקס האחרון.

def runningSum(nums):
    result = []
    for i in range(len(nums)):
        total = 0
        for j in range(i + 1):
            total += nums[j]
        result.append(total)
    return result

עקוב אחר הסכום המצטבר

האינטואיציה

הסכום של i+1 המספרים הראשונים הוא הסכום של i המספרים הראשונים ועוד nums[i]: result[i] = result[i-1] + nums[i]. לכן אף פעם לא צריך לחזור יותר מצעד אחד אחורה, ומשתנה אחד total מספיק. עבור [3, 1, 4, 1, 5] מתקבלים 3, 4, 8, 9, 14, וזו התשובה.

כל איבר דורש חיבור אחד: זמן O(n), ומקום נוסף O(1) מלבד התשובה.

אלגוריתם

צרו מערך תשובות באורך n והגדירו total = 0.
עברו על האינדקסים משמאל לימין והוסיפו את nums[i] אל total.
כתבו את total באינדקס i של מערך התשובות.
החזירו את מערך התשובות.

def runningSum(nums):
    result = []
    total = 0
    for num in nums:
        total += num
        result.append(total)
    return result

מלכודות ומקרי קצה

איפוס total בתוך הלולאה. כל תשובה הופכת ל-nums[i] בלבד, ו-[3, 1, 4] חוזר ללא שינוי.
קריאה של result[i-1] כאשר i = 0. ברוב השפות מתבצעת גישה מחוץ לגבולות; Python קוראת את האיבר האחרון, ולכן גרסה שמשנה את המערך במקום מוסיפה את המספר האחרון לראשון.
עצירת הלולאה הפנימית של שיטת הכוח הגס ב-j < i. כך nums[i] נשאר בחוץ, ולכן בכל תשובה חסר מספר אחד.
ב-R, הרחבת התשובה באמצעות result <- c(result, total) מעתיקה את הווקטור בכל צעד והופכת את הגישה המהירה לריבועית. יש להקצות מראש את האורך המלא.
ב-C, שכחה של *returnSize = numsSize. כתוצאה מכך, הקוד הקורא אינו יודע כמה סכומים לקרוא.

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

מהו הסכום המצטבר של מערך?

זהו מערך שני שבו כל איבר הוא הסכום של כל הערכים עד למיקום הזה, כולל, במערך הראשון. הוא נקרא גם סכום קידומות או סכום מצטבר. הסכום הרץ של [3, 1, 4, 1, 5] הוא [3, 4, 8, 9, 14].

מהי סיבוכיות הזמן של חישוב סכום מצטבר?

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

האם אפשר לחשב את הסכום המצטבר במקום?

כן. עוברים מאינדקס 1 עד הסוף ומגדירים nums[i] += nums[i-1]. עד אז nums[i-1] כבר מכיל את הסכום של כל הערכים עד אליו, ולכן כל איבר מסתיים כסכום הקידומות שלו. הערכים המקוריים הולכים לאיבוד.

איך סכומי קידומות עוזרים בשאילתות סכום לטווח?

הסכום של פרוסה nums[l..r] הוא prefix[r] - prefix[l-1], או prefix[r] כאשר l = 0. עם [3, 4, 8, 9, 14], האינדקסים 2 עד 4 מסתכמים ב־14 - 4 = 10. כל שאילתה אורכת O(1) לאחר מעבר אחד של O(n).

def runningSum(nums):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנט

nums = [3, 1, 4, 1, 5]

הפלט הצפוי

[3, 4, 8, 9, 14]