פתרון לתרגיל ידוע בפייתון

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

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

יש המון דרכים לפתור את התרגיל. דרך מאוד פשוטה היא בסיבוכיות של

O(n^2)

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

עובד? עובד. קל לכתוב? קל.

אבל נניח ואנחנו רוצים לייעל (ותיכף תראו שאפילו לכתוב קוד פשוט וקצר יותר) ולהגיע לריצה ב O של n ? 

הנה הצעה לפתרון:

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

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

יש כאן באג שהשארתי במכוון, מוכנים לנחש מהו ולהציע פתרון?