Running Sum of an Array
ניתן לך מערך של מספרים שלמים nums. החזר מערך חדש באותו אורך, שהאיבר שלו באינדקס i הוא nums[0] + nums[1] + ... + nums[i], הסכום המצטבר לאחר קריאת i+1 המספרים הראשונים משמאל.
פונקציה
- numsinteger-array
- המספרים שיש לחבר משמאל לימין
- מחזירהinteger-array
- הסכומים המצטברים, אחד לכל איבר ב־nums
אילוצים
1 ≤ nums.length ≤ 5000-104 ≤ nums[i] ≤ 104- כל סכום מצטבר מתאים למספר שלם חתום בן 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].
+13 בדיקות נסתרות בשליחה
שאלת המשך
אפשר לבנות את אותו הדבר עבור רשת, שבה כל תא מכיל את הסכום הכולל של המלבן מהפינה השמאלית העליונה ועד לאותו תא?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
מה הקשר בין התשובה באינדקס
iלתשובה באינדקסi-1?שני הסכומים נבדלים במספר אחד בדיוק,
nums[i]. אף פעם לא צריך לחבר שוב את הקידומת מההתחלה.השתמשו במשתנה אחד
total. עברו עלnumsמשמאל לימין, הוסיפו כל מספר אלtotal, וכתבו אתtotalבתשובה באותו אינדקס.
פתרון
כל תשובה היא הסכום של תחילית של nums, ושתי תחיליות שכנות נבדלות בדיוק באיבר אחד. חישוב מחדש של כל תחילית מההתחלה חוזר על כמעט כל העבודה, בעוד ששמירת סכום אחד והעברתו קדימה מספקת כל תשובה בחיבור יחיד. התוצאה היא מערך סכומי התחיליות, הכלי שמאפשר חישוב מהיר של סכומים בטווחים.
חשבו מחדש מההתחלה את הסכום של כל קידומת
האינטואיציה
פעלו לפי ההגדרה מילה במילה. עבור כל אינדקס i, התחילו סכום חדש ב-0, הוסיפו את nums[0] עד nums[i], ושמרו את התוצאה. עבור [3, 1, 4, 1, 5] התשובה האחרונה מחברת את כל חמשת המספרים: 3 + 1 + 4 + 1 + 5 = 14.
זה נכון, אבל יש בו חזרות. הסכום עבור אינדקס 4 מתחיל מחדש מ-nums[0], אף על פי שהסכום עבור אינדקס 3, 9, כבר מכיל את סכום ארבעת המספרים הראשונים. חישוב אינדקס i דורש i+1 פעולות חיבור, ולכן העלות של המערך כולו היא 1 + 2 + ... + n = n(n+1)/2. עבור n = 5000 מדובר בכ-1.25 × 10^7 פעולות חיבור, אף ש-5000 היו מספיקות.
מלבד מערך התשובות, שאותו ממילא מחזירים, נשמרים רק סכום ושני אינדקסים, ולכן המקום הנוסף הוא O(1).
אלגוריתם
- צרו מערך תשובות באורך
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], הערך של total הוא 3, 4, 8, 9, 14, וחמשת הערכים האלה הם התשובה. כל איבר נקרא פעם אחת ונדרשת פעולת חיבור אחת, לכן זמן הריצה הוא O(n). מלבד מערך התשובה, הזיכרון היחיד הוא total, ולכן המקום הנוסף הוא O(1).
אף סכום כאן לא יכול לעלות על 5000 × 10^4 = 5 × 10^7, ולכן הוא נכנס למספר שלם בן 32 סיביות. בקלטים גדולים יותר, סכומים מצטברים הם מקרה קלאסי של גלישת מספרים, ולכן ברירת המחדל הבטוחה היא להשתמש בסכום בן 64 סיביות.
אלגוריתם
- צרו מערך תשובות באורך
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] = result[i-1] + nums[i]בלי לטפל במקרהi = 0. האינדקס-1נמצא מחוץ לטווח ברוב השפות, וב-Python הוא מציין את האיבר האחרון, כך שגרסה שפועלת במקום ומתחילה ב-0 מוסיפה את המספר האחרון לראשון. - עצירת הלולאה הפנימית של הגישה הראשונה ב-
j < i. כךnums[i]לא נכלל, ולכן כל תשובה חסרה מספר אחד. - הגדלת התשובה באמצעות העתקה. ב-R,
result <- c(result, total)מעתיק את כל הווקטור בכל צעד, מה שהופך שוב את הגישה המהירה לריבועית. הקצו מראש את האורך המלא. - שכחת
*returnSize = numsSizeב-C. בלעדיו, הפונקציה הקוראת לא יודעת כמה סכומים לקרוא.
שאלות נפוצות4
מהו הסכום המצטבר של מערך?
זהו מערך שני שבו כל איבר הוא הסכום הכולל של כל הערכים עד למיקום המקביל במערך הראשון, כולל אותו. הוא נקרא גם סכום קידומות או סכום מצטבר. הסכום המצטבר של [3, 1, 4, 1, 5] הוא [3, 4, 8, 9, 14].
מהי סיבוכיות הזמן של חישוב סכום מצטבר?
עם סכום כולל אחד שמועבר משמאל לימין, זמן הריצה הוא O(n), חיבור אחד לכל איבר, ונדרש מקום נוסף של O(1) מלבד התשובה. חישוב מחדש של כל קידומת מההתחלה עולה n(n+1)/2 פעולות חיבור, כלומר 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).
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
Python
def runningSum(nums):
# כתבו כאן קודמקרה 1
מקרה 2
מקרה 3
קלט
nums = [3, 1, 4, 1, 5]
צפוי
[3, 4, 8, 9, 14]