בהינתן מערך של מספרים שלמים (לא בהכרח ממוין, ואין הגבלה על סימן המספר - כלומר יכול להיות חיובי, שלילי או 0), ומספר שלם X, מצא זוג מספרים אשר סכומם X.
כמובן שהכוונה כאן לא הייתה לפתרון הטריוויאלי של n^2 או אפילו nlogn
תשובות
הוסף תשובה
|
לצפיה בתשובות
ינואר 2023
פתרון יעיל בסיבוכיות o(n) הינה:
יצירת סט, מעבר לינארי על הרשימה כך שבכל תא, נשמור בסט את הערך x-A[i] וכך נוכל לדעת האם בן הזוג החסר להשלמת הסכום כבר נמצא ברשימת המספרים