4Sum

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

O(n³). שתי הלולאות בוחרות בערך n²/2 זוגות (i, j) , וכל אחד מהם מקבל סריקה אחת בשיטת שני המצביעים, של לכל היותר n צעדים; המיון O(n log n) קטן לעומת זאת.

Q: איך מכלילים את 4Sum ל־kSum?

כתבו kSum(nums, target, k) על רשימה ממוינת. עבור k = 2 הפונקציה מבצעת סריקה בשני מצביעים. עבור k גדול יותר, היא עוברת בלולאה על הערך הראשון, מדלגת על כפילויות וקוראת לעצמה עם k-1 ועם target - nums[i] על הערכים שמימין. כל רמה מוסיפה גורם של n, ולכן הסיבוכיות של kSum היא O(n^(k-1)).

Q: האם אפשר לפתור את 4Sum ב־O(n²)?

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

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

+10

ניתנת לך רשימה של מספרים שלמים nums ומספר שלם target. החזר כל רביעייה [a, b, c, d] שארבעת הערכים שלה נמצאים בארבעה מיקומים שונים ב־nums וסכומם הוא target. כתוב כל רביעייה כשהערכים שלה מסודרים בסדר לא יורד. אם אפשר לבחור את אותם ארבעת הערכים ממיקומים שונים, הרביעייה עדיין תופיע פעם אחת בלבד. מיין את התשובה לפי הערך הראשון, אחר כך לפי השני, ואז לפי השלישי. אם אין רביעייה מתאימה, החזר רשימה ריקה.

פונקציה

fourSum(nums: integer-array, target: integer) → integer-2d-array

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

אילוצים

1 ≤ nums.length ≤ 200
-10⁸ ≤ nums[i] ≤ 10⁸
-10⁹ ≤ target ≤ 10⁹
הסכום של כל ארבעה ערכים נמצא בטווח שבין -4 × 10⁸ ל־4 × 10⁸, ולכן הוא מתאים למספר שלם בן 32 סיביות.
רביעיות שמכילות את אותם ארבעה ערכים נחשבות לאחת.

דוגמאות

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

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

קלט: nums = [1, 5, 2, 9]target = 3
פלט: []
הסבר: האפשרות היחידה היא כל ארבעת המספרים, ו־1 + 5 + 2 + 9 = 17, לא 3, ולכן התשובה היא רשימה ריקה.

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

נסו כל קבוצה של ארבעה

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

האינטואיציה

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

עבור 200 מספרים יש 64,684,950 קבוצות של ארבעה, והמספר גדל בערך פי 16 כש-n מוכפל.

אלגוריתם

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

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # same first value as the round before
        for j in range(i + 1, n - 2):
            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 - 1):
                if k > j + 1 and nums[k] == nums[k - 1]:
                    continue  # same third value as the round before
                for l in range(k + 1, n):
                    if l > k + 1 and nums[l] == nums[l - 1]:
                        continue  # same fourth value as the round before
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        quads.append([nums[i], nums[j], nums[k], nums[l]])
    return quads

מיון, שתי לולאות, שני מצביעים

האינטואיציה

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

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

בדוגמה הראשונה, כאשר i מצביע על -3 ו־j מצביע על -1, lo מתקדם מ־0, חולף על פני 1 ומגיע ל־2, שם -3 + (-1) + 2 + 3 = 1.

אלגוריתם

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

def fourSum(nums, target):
    nums = sorted(nums)
    n = len(nums)
    quads = []
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # this first value was already handled
        for j in range(i + 1, n - 2):
            if j > i + 1 and nums[j] == nums[j - 1]:
                continue  # this second value was already handled
            lo, hi = j + 1, n - 1
            while lo < hi:
                total = nums[i] + nums[j] + nums[lo] + nums[hi]
                if total < target:
                    lo += 1
                elif total > target:
                    hi -= 1
                else:
                    quads.append([nums[i], nums[j], nums[lo], nums[hi]])
                    lo += 1
                    hi -= 1
                    while lo < hi and nums[lo] == nums[lo - 1]:
                        lo += 1
    return quads

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

דילוג על j בכל פעם ש-nums[j] שווה ל-nums[j-1]. במקרה של j = i+1, משווים לערך שבו משתמש i, ולכן עבור [2, 2, 2, 2, 2] עם יעד 8, הרצף [2, 2, 2, 2] הולך לאיבוד.
העתקה של תנאי היציאה המוקדמת של 3Sum, nums[i] > target. עם [-5, -4, -3, -2, -1] ויעד -10, הלולאה נעצרת ב--5 ומפספסת את [-4, -3, -2, -1].
רשימות שאורכן קטן מארבעה. עם מספר אחד או שניים, n-3 הוא שלילי: 0..<(n - 3) גורם למלכודת ב-Swift, ו-n - 3 מסוג usize ב-Rust גורם לגלישה כלפי מטה. החזירו תחילה רשימה ריקה.
איסוף רביעיות בקבוצת גיבוב והחזרתן ללא מיון.

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

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

O(n³). שתי הלולאות בוחרות בערך n²/2 זוגות (i, j), וכל אחד מהם מקבל סריקה אחת בשיטת שני המצביעים, של לכל היותר n צעדים; המיון O(n log n) קטן לעומת זאת.

איך מכלילים את 4Sum ל־kSum?

כתבו kSum(nums, target, k) על רשימה ממוינת. עבור k = 2 הפונקציה מבצעת סריקה בשני מצביעים. עבור k גדול יותר, היא עוברת בלולאה על הערך הראשון, מדלגת על כפילויות וקוראת לעצמה עם k-1 ועם target - nums[i] על הערכים שמימין. כל רמה מוסיפה גורם של n, ולכן הסיבוכיות של kSum היא O(n^(k-1)).

האם אפשר לפתור את 4Sum ב־O(n²)?

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

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

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

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

הפלט הצפוי

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