Minimum Size Subarray Sum

Q: מהי סיבוכיות הזמן של סכום תת־מערך בגודל מינימלי?

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

Q: למה ללמוד את פתרון הסכום המצטבר O(n log n) אם קיים פתרון O(n)?

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

Q: האם סכום תת-המערך חייב להיות בדיוק target?

לא. כל סכום שגדול מ־ target או שווה לו נחשב. כאשר target = 15 , החלון 9, 3, 7 מסתכם ב־19 ועדיין אורכו 3. אם צריך סכום מדויק במקום זאת, החלון עדיין עובד עבור ערכים חיוביים: מצמצמים אותו כל עוד הסכום גדול מהיעד, ומתעדים אורך רק כשהוא שווה לו.

בינוניחלון נע סכומי תחיליות

+10

ניתנים לך מספר שלם חיובי target ומערך nums של מספרים שלמים חיוביים. מצא את תת־המערך הקצר ביותר (רצף של איברים סמוכים) שסכומו לפחות target, והחזר את אורכו. אם אף תת־מערך אינו מגיע ל־target, החזר 0.

פונקציה

minSubArrayLen(target: integer, nums: integer-array) → integer

targetinteger: הסכום שתת־מערך חייב להגיע אליו או לעבור אותו
numsinteger-array: המערך של מספרים שלמים חיוביים
מחזירהinteger: אורך תת-המערך הקצר ביותר שסכומו לפחות target, או 0 אם אין כזה

אילוצים

1 ≤ target ≤ 10⁹
1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 10⁴

דוגמאות

קלט: target = 15nums = [4, 2, 9, 3, 7, 1, 5]
פלט: 3
הסבר: אין שני מספרים סמוכים שסכומם מגיע ל־15: הסכום הגדול ביותר של זוג הוא 9 + 3 = 12. שלושה כן מגיעים: 4 + 2 + 9 = 15 וגם 9 + 3 + 7 = 19, לכן התשובה היא 3.

+16 בדיקות נסתרות בשליחה

שאלת המשך

איך היית פותר את זה אם nums היה יכול להכיל גם אפסים ומספרים שליליים, כך שחלון ההזזה כבר לא עובד?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

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

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

קבעו אינדקס התחלה והוסיפו ערכים בזה אחר זה ימינה. בפעם הראשונה שהסכום המצטבר מגיע ל־target, יש לכם את תת־המערך הקצר ביותר שמתחיל באותו מקום: כל תת־מערך קצר יותר נעצר קודם לכן, והסכום שלו עדיין היה קטן מדי. לכן תעדו את אורכו, הפסיקו להרחיב ועברו לנקודת ההתחלה הבאה. התשובה היא האורך הקטן ביותר מבין כל נקודות ההתחלה.

עבור target = 15 ו־[4, 2, 9, 3, 7, 1, 5], הסכומים שמתחילים באינדקס 0 הם 4, 6, 15, והחיפוש נעצר באורך 3. באינדקס 1 הסכומים הם 2, 11, 14, 21, והחיפוש נעצר באורך 4. באינדקס 2 הסכומים הם 9, 12, 19, ושוב מתקבל אורך 3. אין נקודת התחלה שמניבה תוצאה טובה יותר מ־3.

הבעיה מתעוררת כשהיעד קשה להשגה. אם אף תת־מערך לא מגיע אליו, כל חיפוש מנקודת התחלה נמשך עד סוף המערך: n(n+1)/2 פעולות חיבור, כלומר 2 × 10^8 עבור n = 2 × 10^4. כל חיפוש מנקודת התחלה גם מחשב מחדש סכומים שכבר חושבו בנקודת ההתחלה הקודמת.

אלגוריתם

הגדר את best ל־0, כלומר עדיין לא נמצא דבר.
עבור כל אינדקס התחלה, הגדר סכום מצטבר ל־0.
הזז אינדקס סיום ימינה מנקודת ההתחלה והוסף את nums[end] לסכום.
כשהסכום מגיע ל־target, שמור את end-start+1 אם הוא גדול מ־best, והפסק להרחיב את נקודת ההתחלה הזאת.
החזר את best.

def minSubArrayLen(target, nums):
    n = len(nums)
    best = 0  # 0 means no subarray found yet
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            if total >= target:
                # The shortest subarray from this start ends here
                if best == 0 or end - start + 1 < best:
                    best = end - start + 1
                break
    return best

סכומי קידומות וחיפוש בינארי

האינטואיציה

נסמן ב־prefix[k] את הסכום של k הערכים הראשונים, כאשר prefix[0] = 0. לכן הסכום של nums[start..end-1] הוא prefix[end] - prefix[start]. עבור ערך קבוע של start, רוצים למצוא את ה־end הקטן ביותר שעבורו prefix[end] ≥ prefix[start] + target.

כל הערכים חיוביים, ולכן prefix עולה ממש, ואפשר למצוא בחיפוש בינארי את המיקום הראשון שבו הוא מגיע לערך מסוים. עבור [4, 2, 9, 3, 7, 1, 5], הערכים של prefix הם [0, 4, 6, 15, 18, 25, 26, 31]. מ־start 2 צריך 6 + 15 = 21; הערך הראשון של prefix שגדול או שווה ל־21 הוא 25 באינדקס 5, ולכן החלון הוא nums[2..4] = 9, 3, 7, באורך 3.

אם אפילו prefix[n] קטן מהערך הנדרש עבור start מסוים, אין end שמתאים לו, וגם לא יהיה end מתאים לאף start מאוחר יותר, כי prefix[start] רק גדל. עוצרים שם. מדובר ב־n חיפושים בינאריים, בזמן O(n log n), ובנוסף O(n) עבור מערך הסכומים המצטברים. הערך הגדול ביותר שמשווים הוא 2 × 10^8 + 10^9, והוא נכנס למספר שלם בן 32 סיביות.

אלגוריתם

בנו את prefix באורך n+1, עם prefix[k+1] = prefix[k] + nums[k].
עבור כל נקודת התחלה, חשבו את need = prefix[start] + target.
אם prefix[n] < need, עצרו: שום נקודת התחלה מאוחרת יותר לא תצליח.
בצעו חיפוש בינארי במיקומים start+1 עד n כדי למצוא את ה-end הראשון שעבורו prefix[end] ≥ need, ושמרו את end-start אם זהו האורך הקצר ביותר עד כה.
החזירו את האורך הקצר ביותר, או 0 אם אף נקודת התחלה לא הצליחה.

from bisect import bisect_left


def minSubArrayLen(target, nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values; it only grows
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    best = 0
    for start in range(n):
        need = prefix[start] + target
        if prefix[n] < need:
            break  # no window from here on can reach target
        # The first end with prefix[end] >= need closes the shortest window
        end = bisect_left(prefix, need, start + 1)
        if best == 0 or end - start < best:
            best = end - start
    return best

חלון הזזה

האינטואיציה

שמרו חלון nums[left..right] ואת הסכום שלו. הזיזו את right צעד אחד בכל פעם והוסיפו את הערך החדש. כל עוד הסכום גדול או שווה ל-target, החלון הוא מועמד: תעדו את אורכו, ואז הסירו את nums[left] והזיזו את left קדימה כדי לבדוק אם חלון קצר יותר עדיין מתאים.

למה אפשר לוותר על left לתמיד? כאשר החלון nums[left..right] מגיע לראשונה ל-target, החלון הקטן יותר nums[left..right-1] לא הגיע אליו, כי הלולאה הייתה מצמצמת אותו בצעד הקודם. לכן right הוא הסוף המוקדם ביותר עבור נקודת ההתחלה הזו, וכל סוף מאוחר יותר יוצר רק תת-מערך ארוך יותר. נקודת ההתחלה הזו כבר הניבה את התשובה הטובה ביותר שלה. הטיעון הזה דורש ערכים חיוביים: עם מספר שלילי, חלון ארוך יותר עשוי לקבל סכום גדול יותר בהמשך.

עבור target = 15 ו-[4, 2, 9, 3, 7, 1, 5]: הסכום עולה ל-4, ל-6, ואז ל-15, ולכן מתעדים אורך 3 ומסירים את 4 (11). הוספת 3 נותנת 14, והוספת 7 נותנת 21: מתעדים אורך 4, מסירים את 2 (19), מתעדים אורך 3 ומסירים את 9 (10). הוספת 1 ו-5 נותנת 16: מתעדים אורך 4 ומסירים את 3 (13). התשובה היא 3.

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

אלגוריתם

הגדר את left = 0, את total = 0 ואת best = 0.
עבור כל right, הוסף את nums[right] ל־total.
כל עוד total ≥ target, שמור את right-left+1 אם הוא עדיף על best, חסר את nums[left] והזז את left צעד אחד ימינה.
החזר את best, שיישאר 0 אם הסכום מעולם לא הגיע ל־target.

def minSubArrayLen(target, nums):
    best = 0  # 0 means no window found yet
    total = 0  # sum of nums[left .. right]
    left = 0
    for right in range(len(nums)):
        total += nums[right]
        # Shrink while the window still reaches target
        while total >= target:
            if best == 0 or right - left + 1 < best:
                best = right - left + 1
            total -= nums[left]
            left += 1
    return best

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

רוב הבאגים נמצאים בשלב הכיווץ ובערך שמחזירים כששום חלון לא מגיע ל־target.

כיווץ באמצעות if במקום while. עבור target = 12 ו־[1, 1, 2, 3, 12], הוספת 12 מביאה את הסכום ל־19. if מתעד אורך 5, מסיר ערך אחד וממשיך הלאה, ולכן החלון [12] שאורכו 1 לעולם לא נמדד. לולאה ממשיכה להסיר ערכים כל עוד הסכום עדיין מספיק.
תיעוד האורך אחרי הסרת nums[left] במקום לפניה. החלון שמודדים חייב להיות זה שסכומו הגיע ל־target.
השוואה באמצעות > במקום ≥. תת־מערך שסכומו שווה ל־target נחשב: עבור [3, 3, 3] עם target = 9, התשובה היא 3, לא 0.
החזרת ערך הסמן. אם מתחילים את best בערך n+1 או באינסוף, יש להמיר אותו ל־0 כששום חלון לא הגיע ל־target.
שימוש חוזר בחלון במערכים עם אפסים או ערכים שליליים. השיטה מסתמכת על כך שכל הערכים חיוביים; הבעיה הזאת מבטיחה זאת, אבל וריאציות לא.

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

מהי סיבוכיות הזמן של סכום תת־מערך בגודל מינימלי?

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

למה חלון ההזזה צריך מספרים חיוביים?

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

למה ללמוד את פתרון הסכום המצטבר O(n log n) אם קיים פתרון O(n)?

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

האם סכום תת-המערך חייב להיות בדיוק target?

לא. כל סכום שגדול מ־target או שווה לו נחשב. כאשר target = 15, החלון 9, 3, 7 מסתכם ב־19 ועדיין אורכו 3. אם צריך סכום מדויק במקום זאת, החלון עדיין עובד עבור ערכים חיוביים: מצמצמים אותו כל עוד הסכום גדול מהיעד, ומתעדים אורך רק כשהוא שווה לו.

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

target = 15
nums = [4, 2, 9, 3, 7, 1, 5]

צפוי

Minimum Size Subarray Sum

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

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

סכומי קידומות וחיפוש בינארי

חלון הזזה

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

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

בעיות דומות