בשאלה זו נתבקש להחזיר את האינדקסים של זוג ספרות המרכיבות סכום נתון במערך נתון.
למשל, עבור מערך המספרים: [3,5,7,1] והמספר 8 נחזיר [2,3] כי הספרות באינדקסים אלה שהם 7 ו-1 מגיעות לסכום 8 ועבור 10 נחזיר False כיוון שלא קיימים זוג ספרות שיכולות להגיע לסכום 10.
המערך אינו ממוין. כמו"כ ניתן להניח שקיים פיתרון יחיד.
דרישות:
- יעילות זמן: n
- יעילות מקום: n
בפעם הראשונה שרואים שאלה מסוג זה, הנטייה האינטואיטיבית היא להתחיל בכיוון של פתרון Brute Force - שזה אומר לחפש את כל הזוגות הקיימים במערך ואז לנסות לחשוב איך לייעל זאת, אך זה לא הכיוון הנכון.
הרמז הראשון נעוץ בכך שמדובר בסכום של שתי ספרות בלבד. זה אומר שאם יש לי ספרה אחת מהמערך, כל מה שאני זקוק לו זה את הספרה המשלימה לסכום.
אם יש לנו ניסיון משאלות קודמות, אנחנו מבינים שאם המערך לא ממוין, אנחנו לא יכולים להשתמש בשיטות חיפוש וכנראה שקיים פתרון יעיל יותר מסתם למיין את המערך ואז לחפש את זוג הספרות.
כדי לחסוך בסיבוכיות הזמן, נשתמש בזיכרון תוך כדי האיטרציה על המערך ונאחסן בו את הספרות שעברנו עליהן ואת האינדקסים שלהן, זה יסייע לנו לשאול ב-O(1) האם קיים מספר מסוים בספרות שפגשנו עד כה ומה האינדקס שלו.
כל מה שנותר הוא לבדוק האם קיים המשלים לסכום מתוך הספרות שעברנו עליהם.
אין תגובות:
הוסף רשומת תגובה