חידה תכנותית: twoSum

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

לדוגמה:

nums = [2,7,3,6]
target = 9

צריך להחזיר:

output = [0,1]

דוגמאות נוספות:

nums = [3,2,4]
target = 6
output = [2, 1]

nums = [4,4]
target = 8
output = [1, 0]

פתרון פחות יעיל בסיבוכיות זמן O(n^2)

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

def two_sum(nums, target):
    # Brute force solution
    for o_idx, o_num in enumerate(nums):
        for i_idx, i_num in enumerate(nums[o_idx+1:]):
            if o_num + i_num == target:
                return [o_idx, i_idx+o_idx+1]

ננסה:

# Test cases
nums = [2,7,3,6]
target = 9
print(two_sum(nums, target)) # [1, 0]

nums = [3,2,4]
target = 6
print(two_sum(nums, target)) # [2, 1]

nums = [4,4]
target = 8
print(two_sum(nums, target)) # [1, 0]

נסביר:

הקוד לעיל הוא פתרון brute force לבעיית Two Sum. הוא עובד על ידי מעבר בתוך לולאות מקוננות על רשימת המספרים, וסכימת המספר הנוכחי מן הלולאה החיצונית עם המספר הנוכחי מן הלולאה הפנימית .

נסביר את הקוד יותר בפירוט:

• הפונקציה two_sum(), מקבלת שני ארגומנטים: מערך מספרים`nums` ומספר מטרה `target`. הפונקציה מחזירה מערך הכולל את האינדקסים של שני מספרים שסכומם שווה ל- `target`, או רשימה ריקה אם לא קיים זוג העונה על הדרישה.

• הלולאה החיצונית:

  for o_idx, o_num inenumerate(nums):

  עוברת על מערך המספרים `nums`, תוך שימוש בפונקציה enumerate() כדי לקבל את האינדקס והערך של כל פריט במערך. המשתנים `o_idx` ו-`o_num` מאחסנים את האינדקס והערך של האלמנט הנוכחי.

• הלולאה הפנימית:

  for i_idx, i_num inenumerate(nums[o_idx+1:]):

  עוברת על תת-רשימת המספרים `nums` החל מהאלמנט שאחרי האלמנט הנוכחי.

• בתוך הלולאה הפנימית ישנו תנאי:

  if o_num + i_num == target:
      return [o_idx, i_idx+o_idx+1]

  • אם הסכום של האלמנט הנוכחי בלולאה החיצונית (`o_num`) והאלמנט הנוכחי בלולאה הפנימית (`i_num`) שווה לסכום היעד אז הפונקציה מחזירה מערך המכיל את האינדקסים של שני מספרים אלה.
  • האינדקס של המספר הראשון הוא `o_idx`, והאינדקס של המספר השני הוא i_idx+o_idx+1. הסיבה לכך היא שהלולאה הפנימית מתחילה מהאלמנט שאחרי האלמנט הנוכחי בלולאה החיצונית, לכן אנו צריכים להוסיף o_idx+1 ל-`i_idx` כדי לקבל את האינדקס הנכון של המספר השני.
  • אם לא מוצאים זוג מספרים ברשימה `nums` שסכומם `target`, הלולאה הפנימית תסיים את ביצועה ללא החזרה. הלולאה החיצונית תמשיך לאחר מכן לאלמנט הבא ברשימה `nums`. אם הלולאה החיצונית תסיים את ביצועה ללא החזרה, זה אומר שאין זוג שסכומו שווה ל- `target`, ועל כן הפונקציה תחזיר רשימה ריקה.

הפתרון הזה הוא brute force ודורש סיבוכיות זמן O(n^2) מכיוון שהוא משתמש בלולאות מקוננות לצורך סכימת כל פריט במערך `nums` עם פריטי המערך הנותרים. אבל ישנו פתרון יעיל יותר.

אלגוריתם יעיל לפתרון אתגר twoSum בעל סיבוכיות זמן O(n)

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

להלן הפתרון המשופר:

def two_sum(nums, target):
    # Create a dictionary to store the complementaries
    complementaries_indexes = {}
    
    # Iterate through the list
    for idx, num in enumerate(nums):
        # Calculate the complementary needed to reach the target
        complementary = target-num
        
        # If the complementary is in the dictionary, return its index and the current index
        if num in complementaries_indexes:
            return [idx, complementaries_indexes[num]]
        
        # Otherwise, store the current complementary and index in the dictionary
        complementaries_indexes[complementary] = idx
     
    # If no solution is found, return an empty list       
    return []

ננסה את הפתרון המשופר:

# Test cases
nums = [2,7,3,6]
target = 9
print(two_sum(nums, target)) # [1, 0]

nums = [1,4,3,6]
target = 9
print(two_sum(nums, target)) # [2,3]

nums = [3,2,4]
target = 6
print(two_sum(nums, target)) # [2, 1]

nums = [4,4]
target = 8
print(two_sum(nums, target)) # [1, 0]

nums = [4,4]
target = 9
print(two_sum(nums, target)) # []

נסביר:

האלגוריתם עובד באופן הבא:

1. יוצר מילון לאחסון ההפרש של המספרים ברשימת הקלט מה-`target`.
2. עובר בלולאה על כל מספר ברשימת הקלט:
• מחשב את ההפרש מהיעד `target`.
• אם ההפרש נמצא במילון, מחזיר את האינדקסים של שני המספרים.
• אחרת, מאחסן את ההפרש ואת האינדקס של המספר הנוכחי במילון.
3. אם לא נמצא פתרון, מחזיר רשימה ריקה.

נסביר את הקוד:

• מגדירים פונקציה בשם two_sum שלוקחת שני ארגומנטים: `nums`, שהוא רשימת המספרים, ו-`target`, שהוא סכום היעד שאנחנו רוצים להשיג.

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

  # Create a dictionary to store the complementaries
  complementaries_indexes = {}

• לולאה עוברת על רשימת המספרים `nums`, באמצעות enumerate() כדי לקבל גם את האינדקס (idx) וגם את המספר (num) בכל עמדה. בכל איטרציה, מחשבים את ההפרש הדרוש כדי להגיע לסכום היעד:

  # Iterate through the list
  for idx, num in enumerate(nums):
      # Calculate the complementary needed to reach the target
      complementary = target-num

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

    # If the complementary is in the dictionary, return its index and the current index
    if num in complementaries_indexes:
        return [idx, complementaries_indexes[num]]

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

    # Otherwise, store the current complementary and index in the dictionary 
    complementaries_indexes[complementary] = idx

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

הערכת ביצועים:

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

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

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

טכניקת חלון ההזזה sliding window לפתרון בעיות ברצפים

שימוש בטכניקות שני המצביעים לפתרון בעיות תכנותיות

big-O ביטוי ליעילות הקוד

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים