Two Sum II: Sorted Input

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

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

Q: מהי סיבוכיות הזמן של Two Sum II?

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

Q: למה לא להשתמש במפת גיבוב כמו ב־Two Sum הראשון?

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

Q: מתי חיפוש בינארי הוא הבחירה הטובה יותר כאן?

כשערך אחד קבוע ואתה זקוק רק לבן הזוג שלו. אם numbers[0] חייב להופיע בזוג, חיפוש בינארי אחד מוצא את האינדקס השני ב־ O(log n) . כדי למצוא זוג לא ידוע, סריקה באמצעות שני מצביעים מהירה יותר מ־ n חיפושים נפרדים.

קלשני מצביעים חיפוש בינארי

+10

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

פונקציה

twoSumSorted(numbers: integer-array, target: integer) → integer-array

numbersinteger-array: מערך המספרים השלמים הממוינים
targetinteger: הסכום שאליו שני הערכים חייבים להגיע
מחזירהinteger-array: שני האינדקסים המתחילים ב־0 [i, j] כך ש־i < j ו־numbers[i] + numbers[j] == target

אילוצים

2 ≤ numbers.length ≤ 10⁴
-5 × 10⁸ ≤ numbers[i] ≤ 5 × 10⁸
-10⁹ ≤ target ≤ 10⁹
numbers מסודר בסדר לא יורד.
בדיוק זוג אחד של אינדקסים i < j מקיים numbers[i] + numbers[j] == target.

דוגמאות

קלט: numbers = [-4, 1, 3, 8, 12]target = 9
פלט: [1, 3]
הסבר: 1 נמצא באינדקס 1 ו-8 באינדקס 3, ו-1 + 8 = 9. שום זוג אחר לא מגיע ל-9: לדוגמה, -4 + 12 = 8.

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

שאלת המשך

האם תוכל לפתור זאת בזמן O(n) ובשימוש בזיכרון נוסף של O(1)?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

בדוק כל זוג

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

האינטואיציה

נסו כל זוג של מיקומים i < j ובדקו אם numbers[i] + numbers[j] שווה ל־target. מכיוון ש־i מתקדם משמאל ו־j מתחיל מיד אחריו, הזוג הראשון שתמצאו כבר מציב את האינדקס הקטן יותר ראשון.

הפתרון נכון, אבל הוא מתעלם מכך שהמערך ממוין. כאשר n = 10^4, יש בערך 5 × 10^7 זוגות, וכשהתשובה נמצאת סמוך לסוף המערך, בודקים כמעט את כולם. זה איטי מדי עבור הבדיקות הגדולות.

אלגוריתם

עבור בלולאה על i בכל האינדקסים.
עבור בלולאה על j מ־i+1 ועד לאינדקס האחרון.
אם numbers[i] + numbers[j] שווה ל־target, החזר את [i, j].

def twoSumSorted(numbers, target):
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i, j]
    return []

חיפוש בינארי עבור כל שותף

האינטואיציה

אחרי שמקבעים את הערך הראשון numbers[i], יודעים בדיוק מיהו הערך המתאים לו: target - numbers[i]. החלק של המערך שמימין ל־i ממוין, ולכן חיפוש בינארי יכול לקבוע בתוך O(log n) צעדים אם הערך המתאים נמצא בו.

עבור [-4, 1, 3, 8, 12] ו־target = 9: ב־i = 0 הערך המתאים היה 13, והוא חסר. ב־i = 1 הערך המתאים הוא 8, והחיפוש מוצא אותו באינדקס 3. התשובה היא [1, 3].

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

אלגוריתם

עבור בלולאה על i מ־0 עד n-2.
חשב את need = target - numbers[i].
בצע חיפוש בינארי אחר need באינדקסים i+1 עד n-1.
אם מצאת אותו ב־mid, החזר את [i, mid].

def twoSumSorted(numbers, target):
    n = len(numbers)
    for i in range(n - 1):
        need = target - numbers[i]
        lo, hi = i + 1, n - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            if numbers[mid] == need:
                return [i, mid]
            if numbers[mid] < need:
                lo = mid + 1
            else:
                hi = mid - 1
    return []

שני מצביעים משני הקצוות

האינטואיציה

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

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

עבור [-4, 1, 3, 8, 12] עם target = 9: ‏-4 + 12 = 8 קטן מדי, לכן left עובר לאינדקס 1. לאחר מכן 1 + 12 = 13 גדול מדי, לכן right עובר לאינדקס 3. עכשיו 1 + 8 = 9, והתשובה היא [1, 3].

אלגוריתם

הגדר את left ל־0 ואת right ל־n-1.
כל עוד left < right, חשב את total = numbers[left] + numbers[right].
אם total שווה ל־target, החזר את [left, right].
אם total קטן יותר, הוסף 1 ל־left; אם הוא גדול יותר, הפחת 1 מ־right.

def twoSumSorted(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left, right]
        if total < target:
            left += 1  # need a bigger sum
        else:
            right -= 1  # need a smaller sum
    return []

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

הלולאה עם שני מצביעים קצרה, ולכן הבאגים מסתתרים בפרטים שסביבה.

החזרת מיקומים שמתחילים ב-1. הגרסה הזו דורשת אינדקסים שמתחילים ב-0: עבור [-4, 1, 3, 8, 12] ו-target = 9 התשובה היא [1, 3], ולא [2, 4]. ב-Lua וב-R, יש להפחית 1 לפני שמחזירים את התוצאה.
שימוש בתנאי הלולאה left <= right. כשהמצביעים נפגשים, הסכום ישתמש באותו ערך פעמיים.
הזזת המצביע הלא נכון. סכום קטן מדי דורש ערך גדול יותר, ורק left יכול לספק אותו.
דחיית ערכים כפולים. במקרה של [2, 2, 5, 7] עם target = 4, משתמשים בשני ערכי ה-2, שנמצאים במיקומים שונים.
גלישת מספר שלם. המגבלות כאן מבטיחות שכל סכום יישאר בטווח של מספר שלם בן 32 סיביות. אם הערכים יכלו להגיע ל-10^9, יש לחבר אותם באמצעות טיפוס בן 64 סיביות.

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

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

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

מהי סיבוכיות הזמן של Two Sum II?

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

למה לא להשתמש במפת גיבוב כמו ב־Two Sum הראשון?

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

מתי חיפוש בינארי הוא הבחירה הטובה יותר כאן?

כשערך אחד קבוע ואתה זקוק רק לבן הזוג שלו. אם numbers[0] חייב להופיע בזוג, חיפוש בינארי אחד מוצא את האינדקס השני ב־O(log n). כדי למצוא זוג לא ידוע, סריקה באמצעות שני מצביעים מהירה יותר מ־n חיפושים נפרדים.

Python

def twoSumSorted(numbers, target):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

numbers = [-4, 1, 3, 8, 12]
target = 9

צפוי

[1, 3]

Two Sum II: Sorted Input

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

בדוק כל זוג

חיפוש בינארי עבור כל שותף

שני מצביעים משני הקצוות

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

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

בעיות דומות