Two Sum

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

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

Q: האם אפשר לפתור את בעיית סכום של שניים בלי להשתמש במקום נוסף?

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

קלגיבוב

+10

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

פונקציה

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

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

אילוצים

2 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
-10⁹ ≤ target ≤ 10⁹
זוג אחד בדיוק של מיקומים שונים מסתכם ב־target.

דוגמאות

קלט: nums = [3, 8, 12, 5]target = 17
פלט: [2, 3]
הסבר: 12 נמצא באינדקס 2 ו־5 באינדקס 3, ו־12 + 5 = 17. אף זוג אחר לא מגיע ל־17.

שאלת המשך

אם nums כבר הגיע ממוין, האם תוכל למצוא את הזוג בזמן O(n) ועם זיכרון נוסף של O(1) בלבד?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

בדוק כל זוג

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

האינטואיציה

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

n מספרים יוצרים בערך n²/2 זוגות: n = 10^4 פירושו קרוב ל-5 × 10^7 חיבורים.

אלגוריתם

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

def twoSum(nums, target):
    n = len(nums)
    for i in range(n):
        # Only look at partners to the right, so each pair is checked once.
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

מעבר אחד עם מפת גיבוב

האינטואיציה

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

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

אלגוריתם

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

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i
    return []

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

שמירת מספר לפני חיפוש המספר המשלים שלו. עם [4, 2, 6] ו-target = 8, המספר 4 מוצא את עצמו ומחזירים [0, 0].
החזרת האינדקסים בסדר שגוי. כשמחפשים לפני ששומרים, האינדקס מהמפה הוא הקטן יותר והוא מופיע ראשון.
מיון המערך כדי להשתמש בשני מצביעים, ואז החזרת המיקומים בעותק הממוין. השאירו את האינדקס המקורי של כל ערך לצדו.
הנחה שהערכים חיוביים או שונים זה מזה. עבור [0, 7, -3, 0] עם target = 0, שני האפסים משלימים זה את זה: [0, 3].
ב-Lua וב-R, החזרת האינדקסים שמתחילים ב-1. חסרו 1 מכל אחד מהם.

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

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

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

האם אפשר לפתור את בעיית סכום של שניים בלי להשתמש במקום נוסף?

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

איך Two Sum מתמודד עם מספרים כפולים?

כפילויות עובדות כשמחפשים את המספר המשלים לפני ששומרים את המספר הנוכחי. ב-[7, 3, 7] עם target = 14, ה-7 הראשון נשמר באינדקס 0 וה-7 השני מוצא אותו, וכך מתקבל [0, 2]. 7 יחיד לעולם לא יוצר זוג עם עצמו: הוא עדיין לא נמצא במפה כשמחפשים אותו.

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

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

nums = [3, 8, 12, 5]
target = 17

הפלט הצפוי

[2, 3]