3Sum

+10

ניתנת לך רשימה של מספרים שלמים nums. מצא כל שלשה [a, b, c] של ערכים שנלקחו משלושה מיקומים שונים ב-nums, כך ש-a + b + c = 0. כתוב כל שלשה בסדר לא יורד (a ≤ b ≤ c) והצג כל שלשה ייחודית פעם אחת, גם אם כמה בחירות של מיקומים יוצרות אותה. החזר את השלשות ממוינות לפי הערך הראשון שלהן, ואז לפי השני.

פונקציה

threeSum(nums: integer-array) → integer-2d-array

numsinteger-array: רשימת המספרים השלמים, עם לפחות שלושה איברים
מחזירהinteger-2d-array: כל שלשה ייחודית שסכומה 0, כאשר כל שלשה מסודרת בסדר לא־יורד והרשימה ממוינת

אילוצים

3 ≤ nums.length ≤ 3000
-10⁵ ≤ nums[i] ≤ 10⁵
לפחות שלשה אחת מסתכמת ב־0.
שתי שלשות זהות כאשר הן מכילות את אותם שלושת הערכים.

דוגמאות

קלט: nums = [-2, 0, 1, 1, -1, 2]
פלט: [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
הסבר: -2 + 0 + 2, -2 + 1 + 1 וגם -1 + 0 + 1 שווים כולם ל-0. [-2, 1, 1] יכולה להשתמש בערך 1 פעמיים כי 1 מופיע בשני מקומות, ואילו אפשר לבנות את [-1, 0, 1] באמצעות אחד מהערכים 1, אבל הוא מופיע פעם אחת.

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

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

שאלת המשך

אותה תבנית פותרת את 4Sum: מקבעים שני ערכים ומפעילים שני מצביעים על השאר. האם תוכל לכתוב זאת ב־O(n³) ולשמור על כללי הסרת הכפילויות בכל רמה?

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

נסו כל שלשה

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

האינטואיציה

ממיינים קודם את הרשימה. לאחר מכן, כל שלושה מיקומים i < j < k נותנים ערכים שכבר מסודרים לפי הסדר, nums[i] ≤ nums[j] ≤ nums[k], כך ששלשה נכתבת נכון ברגע שמוצאים אותה. שלוש לולאות מקוננות עוברות על כל בחירה של מיקומים, ולכן אי אפשר לפספס אף שלשה.

עכשיו מטפלים בערכים חוזרים. הדוגמה הראשונה לאחר מיון היא [-2, -1, 0, 1, 1, 2], ואת הערך 1 בשלשה [-1, 0, 1] אפשר לקחת מאינדקס 3 או מאינדקס 4. לכן כל לולאה מדלגת על מיקום שהערך בו זהה לערך שהלולאה ניסתה קודם. כל לולאה מנסה כך כל ערך ייחודי פעם אחת, וכל שלשה ייחודית מופיעה פעם אחת, כבר בסדר ממוין. הדילוג משווה רק למיקום הקודם בתוך אותה לולאה, ולכן [-2, 1, 1] עדיין משתמש בשני הערכים 1.

הבעיה היא העלות. יש בערך n³/6 שלשות: עבור 3000 מספרים מדובר ב-4.5 × 10^9 סכומים, הרבה מעבר לכל מגבלת זמן.

אלגוריתם

מיין את nums.
עבור עם לולאה על i לאורך המיקומים, ודלג על i כאשר nums[i] שווה ל־nums[i-1].
בתוך הלולאה, עבור עם לולאה על j החל מ־i+1, ודלג על j כאשר j > i+1 וגם nums[j] שווה ל־nums[j-1].
בתוך הלולאה הזאת, עבור עם לולאה על k החל מ־j+1 עם אותו כלל דילוג, ורשום את [nums[i], nums[j], nums[k]] כאשר שלושתם מסתכמים ל־0.
החזר את השלשות בסדר שבו מצאת אותן. הן כבר ממוינות.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 1):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # same second value as the round before
            for k in range(j + 1, n):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                if nums[i] + nums[j] + nums[k] == 0:
                    triplets.append([nums[i], nums[j], nums[k]])
    return triplets

תקנו ערך אחד, מצאו את הזוג באמצעות קבוצת גיבוב

האינטואיציה

לאחר שקובעים את הערך הראשון nums[i], צריך שני ערכים מאוחרים יותר שסכומם -nums[i]. זהו Two Sum. עוברים עם j ימינה מ-i ושומרים קבוצה של הערכים שכבר עברתם. בכל j, הערך החסר הוא need = -nums[i] - nums[j]. אם need נמצא בקבוצה, הסכום של [nums[i], need, nums[j]] הוא 0. חיפוש בקבוצה עולה בממוצע O(1), לכן עבור i אחד העלות היא O(n), והחיפוש כולו עולה O(n²).

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

פרט אחד: ככל ש-j מתקדם ימינה, nums[j] גדל ו-need קטן, ולכן השלשות עבור i אחד מתקבלות כשהערך האמצעי הולך וקטן. ב-[-2, -1, 0, 1, 1, 2] כאשר i = 0, מוצאים את [-2, 1, 1] ב-1 השני, ואז את [-2, 0, 2] ב-2. הופכים את הסדר בכל קבוצה לפני שמוסיפים אותה לתשובה. גרסאות C ו-R מסמנות ערכים שכבר נראו במערך שמאונדקס לפי ערך, במקום להשתמש בקבוצת גיבוב, והדבר עובד משום שכל ערך נמצא בטווח ±10^5.

אלגוריתם

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

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        group = []
        seen = set()  # values between position i and position j
        j = i + 1
        while j < n:
            need = -nums[i] - nums[j]
            if need in seen:
                group.append([nums[i], need, nums[j]])
                while j + 1 < n and nums[j + 1] == nums[j]:
                    j += 1
            seen.add(nums[j])
            j += 1
        # need shrinks as nums[j] grows, so this group came out backwards
        group.reverse()
        triplets.extend(group)
    return triplets

מיון ושימוש בשני מצביעים

האינטואיציה

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

אף שלשה לא הולכת לאיבוד. כשהסכום קטן מ-0, גם עם הערך הגדול ביותר שנותר, nums[hi], הערך nums[lo] עדיין קטן מדי, ולכן הוא לא יכול ליצור זוג עם שום ערך שעדיין נמצא בטווח, והסרתו לא גורעת דבר. כשהסכום גדול מ-0 זהו המקרה ההפוך: nums[hi] גדול מדי גם עם הערך הקטן ביותר שנותר. בכל צעד מסירים ערך אחד לצמיתות, ולכן עבור i אחד נדרשים לכל היותר n צעדים, ולחיפוש כולו נדרשים O(n²), ללא זיכרון נוסף מעבר למיון ולפלט.

קחו את [-2, -1, 0, 1, 1, 2] הממויין. כאשר i = 0 (הערך -2), lo מתחיל ב--1 ו-hi ב-2: הסכום הוא -1, ולכן lo מתקדם ל-0. כעת -2 + 0 + 2 = 0, ולכן שומרים את [-2, 0, 2], ושני המצביעים מגיעים לשני ערכי ה-1, שיוצרים את [-2, 1, 1]. כאשר i = 1 (הערך -1), 0 ו-2 נותנים 1, ולכן hi מתקדם לערך ה-1 השני, ו--1 + 0 + 1 = 0 שומר את [-1, 0, 1]. הערך 0 ב-i = 2 לא מוצא דבר, וב-i = 3 הערך חיובי, ולכן החיפוש נעצר.

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

אלגוריתם

מיינו את nums.
עבור כל i, עצרו כשמתקיים nums[i] > 0 ודלגו על i כש-nums[i] שווה ל-nums[i-1].
קבעו lo = i+1 ו-hi = n-1. כל עוד מתקיים lo < hi, חברו את nums[i], את nums[lo] ואת nums[hi].
אם הסכום קטן מ-0, הזיזו את lo ימינה. אם הוא גדול מ-0, הזיזו את hi שמאלה.
אם הסכום הוא 0, תעדו את השלשה, הזיזו את שני המצביעים, ואז הזיזו את lo מעבר להעתקים של הערך שבו השתמש.
החזירו את השלשות. הן כבר ממוינות.

def threeSum(nums):
    nums = sorted(nums)
    n = len(nums)
    triplets = []
    for i in range(n - 2):
        if nums[i] > 0:
            break  # the two values after it are at least as large
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        lo, hi = i + 1, n - 1
        while lo < hi:
            total = nums[i] + nums[lo] + nums[hi]
            if total < 0:
                lo += 1
            elif total > 0:
                hi -= 1
            else:
                triplets.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return triplets

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

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

דילוג על i כאשר nums[i] שווה ל־nums[i+1] משאיר את העותק האחרון של כל ערך בתור האיבר הראשון, והעותקים שלפניו נעלמים. ב־[-1, -1, 2] הדבר מאבד את [-1, -1, 2]. השוו למיקום הקודם, nums[i-1].
עצירה כאשר nums[i] ≥ 0 במקום nums[i] > 0 מפספסת את [0, 0, 0].
הסרת הערכים החוזרים בסוף במקום לדלג עליהם. עם 3000 אפסים, לולאת שני המצביעים מתעדת מיליוני עותקים של [0, 0, 0] לפני כל ניקוי, ובכמה שפות קבוצה של רשימות משווה בין הרשימות לפי זהות, כך שהעותקים נשארים בכל מקרה.
שימוש באותו מיקום פעמיים. גרסה המשתמשת בקבוצת גיבוב שממלאת את הקבוצה מראש בכל הרשימה הופכת את [-2, 1, 3] ל־[-2, 1, 1] באמצעות שימוש באחד היחיד פעמיים. חפשו ערכים רק במיקומים שכבר עברתם עליהם.
החזרת השלשות בסדר שגוי. ההשוואה מדויקת, לכן גרסת קבוצת הגיבוב חייבת להפוך כל קבוצה, ופתרון שאוסף שלשות בקבוצה חייב למיין אותן בסוף.

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

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

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

איך 3Sum מונע יצירה של שלשות כפולות?

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

האם כדאי להשתמש בשני מצביעים או בקבוצת גיבוב עבור 3Sum?

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

האם אפשר לפתור את 3Sum בזמן מהיר יותר מ־O(n²)?

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

קלט

nums = [-2, 0, 1, 1, -1, 2]

צפוי

[[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]

3Sum

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

נסו כל שלשה

תקנו ערך אחד, מצאו את הזוג באמצעות קבוצת גיבוב

מיון ושימוש בשני מצביעים

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

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

בעיות דומות