נתון מערך חד-ממדי nums המלא במספרים שלמים לא שליליים (חיוביים ואפסים), ומספר שלם target יש לבדוק אם קיים תת-מערך (רציף) במערך nums שסכום איבריו הוא target אם יש כזה, יש להדפיס את האינדקסים של גבולות התת-מערך.
אם יש כמה תת-מערכים שסכומם הוא target יודפסו הגבולות של התת-מערך שמתחיל באינדקס הנמוך ביותר. אם יש כמה שמתחילים באותו אינדקס, יודפסו הגבולות של זה מביניהם שמסתיים באינדקס הנמוך ביותר.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.
nums = [2, 6, 0, 1, 9, 7, 3, 1, 4, 1, 8], target = 15
Subarray found between indexes 5 and 8 with sum 15
הסבר: הסכום של איברי התת-מערך שמתחיל באינדקס 5 ומסתיים באינדקס 8 הוא 15=7+3+1+4
nums = [2, 6, 0, 1, 9, 7, 3, 1, 4, 1, 8], target = 16
Subarray found between indexes 1 and 4 with sum 16
הסבר: ישנם 3 תת-מערכים שהסכום של איבריהם הוא 16: o מתחיל באינדקס 1 ומסתיים באינדקס 4 והסכום הוא 16=6+0+1+9 o מתחיל באינדקס 4 ומסתיים באינדקס 5 והסכום הוא 16=9+7 o מתחיל באינדקס 5 ומסתיים באינדקס 9 והסכום הוא 16=7+3+1+4+1 ולכן השיטה תדפיס את האינדקסים של התת-מערך הראשון.
nums = [2, 6, 0, 1, 9, 7, 3, 1, 4, 1, 8], target = 8
Subarray found between indexes 0 and 1 with sum 8
הסבר: ישנם 4 תת-מערכים שהסכום של איבריהם הוא 8: o מתחיל באינדקס 0 ומסתיים באינדקס 1 והסכום הוא 8=2+6 o מתחיל באינדקס 0 ומסתיים באינדקס 2 והסכום הוא 8=2+6+0 o מתחיל באינדקס 6 ומסתיים באינדקס 8 והסכום הוא 8=3+1+4 o מתחיל באינדקס 10 ומסתיים באינדקס 10 וערכו 8 ולכן השיטה תדפיס את האינדקסים של התת-מערך הראשון.
nums = [2, 6, 0, 1, 9, 7, 3, 1, 4, 1, 8], target = 22
No subarray found with sum 22
הסבר: אין תת-מערך שסכום איבריו הוא 22.
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], target = 15
Subarray found between indexes 0 and 4 with sum 15
הסבר: הסכום של איברי התת-מערך שמתחיל באינדקס 0 ומסתיים באינדקס 4 הוא 15=1+2+3+4+5. ישנם תת-מערכים נוספים עם סכום 15, למשל [4,5,6], [5,10], [7,8], אבל התת-מערך שמתחיל באינדקס הנמוך ביותר הוא [1,2,3,4,5].
nums = [9, 9, 9, 9, 9], target = 9
Subarray found between indexes 0 and 0 with sum 9
הסבר: כל אחד מהאיברים במערך הוא 9, ולכן התת-מערך שמתחיל ומסתיים באינדקס 0 מקיים את התנאי. זהו התת-מערך שמתחיל באינדקס הנמוך ביותר.
nums = [0, 0, 0, 0, 5], target = 5
Subarray found between indexes 0 and 4 with sum 5
הסבר: למרות שישנו תת-מערך המורכב רק מהאיבר באינדקס 4 שסכומו 5, הפתרון יחזיר את התת-מערך המתחיל באינדקס הנמוך ביותר, שהוא התת-מערך מאינדקס 0 עד 4 עם סכום 5=0+0+0+0+5.
nums = [1, 1, 1, 1, 1, 1, 1, 1], target = 3
Subarray found between indexes 0 and 2 with sum 3
הסבר: ישנם מספר תת-מערכים שסכומם 3, אך התת-מערך שמתחיל באינדקס הנמוך ביותר הוא מאינדקס 0 עד 2 עם הערכים [1,1,1] וסכום 3.
קלט:
nums = [2, 6, 0, 1, 9, 7, 3, 1, 4, 1, 8], target = 15
הפלט המבוקש:
Subarray found between indexes 5 and 8 with sum 15