תת-מערך שגדול ממספר באורך הקצר ביותר

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

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

השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום.

אילוצים:
  • קיימת תשובה אחת חוקית ויש חשיבות לסדר ההדפסות
דוגמה 1:
קלט: 
nums = [2, 6, 1, 9, 7, 3, 1, 4, 1, 8],
target = 15
פלט: 
Subarray found [0-3]
Subarray found [1-3]
Subarray found [2-4]
Subarray found [3-4]
Subarray found [4-8]
Subarray found [5-9]
Smallest Subarray found [3-4]
2

הסבר: ישנם כמה תת-מערכים שהסכום של איבריהם גדול מ-15. התת מערך באורך המינמלי הוא זה המתחיל באינדקס 3 ומסתיים ב-4, כלומר באורך 2.

דוגמה 2:
קלט: 
nums = [2, 6, 1, 9, 7, 3, 1, 4, 1, 8],
target = 100
פלט: 
No Subarray exists
0

הסבר: אין תת-מערך שסכום איבריו גדול מ-100.

דוגמה 3:
קלט: 
nums = [1, 2, 3, 4, 5],
target = 9
פלט: 
Subarray found [0-3]
Subarray found [1-4]
Subarray found [2-4]
Smallest Subarray found [2-4]
3

הסבר: התת-מערך [3, 4, 5] באורך 3 הוא הקטן ביותר שסכומו גדול מ-9.

דוגמה 4:
קלט: 
nums = [5, 1, 3, 5, 10, 7, 4, 9, 2, 8],
target = 15
פלט: 
Subarray found [0-4]
Subarray found [1-4]
Subarray found [2-4]
Subarray found [3-5]
Subarray found [4-5]
Subarray found [5-7]
Subarray found [6-9]
Subarray found [7-9]
Smallest Subarray found [4-5]
2

הסבר: התת-מערך [10, 7] באורך 2 הוא הקטן ביותר שסכומו גדול מ-15.

דוגמה 5:
קלט: 
nums = [20, 18, 4, 5, 3],
target = 17
פלט: 
Subarray found [0-0]
Subarray found [1-1]
Smallest Subarray found [0-0]
1

הסבר: התת-מערך [20] באינדקס 0 בעצמו סכומו גדול מ-17, לכן הוא התת-מערך הקטן ביותר באורך 1.

דוגמה 6:
קלט: 
nums = [1, 4, 16, 22, 5, 7, 8, 9, 10],
target = 20
פלט: 
Subarray found [0-2]
Subarray found [1-3]
Subarray found [2-3]
Subarray found [3-3]
Subarray found [4-7]
Subarray found [5-7]
Subarray found [6-8]
Smallest Subarray found [3-3]
1

הסבר: התת-מערך [22] באינדקס 3 בעצמו סכומו גדול מ-20, לכן הוא התת-מערך הקטן ביותר באורך 1.

דוגמה 7:
קלט: 
nums = [1, 2, 3],
target = 15
פלט: 
No Subarray exists
0

הסבר: אין תת-מערך שסכומו גדול מ-15, לכן התוצאה היא 0.

דוגמה 8:
קלט: 
nums = [3, 1, 7, 11, 2, 9, 8, 21, 6],
target = 20
פלט: 
Subarray found [0-3]
Subarray found [1-4]
Subarray found [2-5]
Subarray found [3-5]
Subarray found [4-7]
Subarray found [5-7]
Subarray found [6-7]
Subarray found [7-7]
Smallest Subarray found [7-7]
1

הסבר: התת-מערך [21] באינדקס 7 בעצמו סכומו גדול מ-20, לכן הוא התת-מערך הקטן ביותר באורך 1.

Loading...
נשמרLn 1, Col 1

קלט:

nums = [2, 6, 1, 9, 7, 3, 1, 4, 1, 8],
target = 15

הפלט המבוקש:

Subarray found [0-3]
Subarray found [1-3]
Subarray found [2-4]
Subarray found [3-4]
Subarray found [4-8]
Subarray found [5-9]
Smallest Subarray found [3-4]
2