בהינתן מערך חד-ממדי arr המלא במספרים שלמים הממוינים בסדר עולה ממש, ומספר שלם num.יש להחזיר כמה שלשות של מספרים יש במערך arr שהסכום שלהם קטן ממש מ־num.
המספרים בשלשות הם לא בהכרח מספרים עוקבים, ולא בהכרח נמצאים בתאים רצופים.
arr והערך num = 2:| 0 | 1 | 2 | 3 |
| -2 | 0 | 1 | 3 |
יוחזר הערך 2 שכן אלו השלשות שהסכום של כל אחת מהן קטן ממש מ־2:
(-2, 0, 3), (-2, 0, 1)
arr והערך num = 12:| 0 | 1 | 2 | 3 | 4 |
| 1 | 3 | 4 | 5 | 7 |
יוחזר הערך 4 שכן אלו השלשות שהסכום של כל אחת מהן קטן ממש מ־12:
(1, 4, 5), (1, 3, 7), (1, 3, 5), (1, 3, 4)
שימו לב שהסכום של השלשה (1, 4, 7) הוא בדיוק 12 ולכן היא לא נספרת.
השיטה צריכה להיות יעילה ככל הניתן, גם מבחינת סיבוכיות הזמן וגם מבחינת סיבוכיות המקום. רמז: הסיבוכיות הנדרשת כאן היא ריבועית.
המערך מכיל מספרים שלמים שונים זה מזה והוא ממוין בסדר עולה ממש.
arr = [-2, 0, 1, 3], num = 2
2
הסבר: השלישיות שסכומן קטן מ-2 הן: (-2, 0, 1) עם סכום -1, ו-(-2, 0, 3) עם סכום 1
arr = [1, 3, 4, 5, 7], num = 12
4
הסבר: השלישיות שסכומן קטן מ-12 הן: (1, 3, 4) עם סכום 8, (1, 3, 5) עם סכום 9, (1, 3, 7) עם סכום 11, (1, 4, 5) עם סכום 10
arr = [1, 2, 3], num = 7
1
הסבר: השלישייה היחידה (1, 2, 3) עם סכום 6 קטנה מ-7
arr = [1, 2, 3], num = 6
0
הסבר: השלישייה (1, 2, 3) עם סכום 6 שווה ל-6 ולא קטנה ממנו
arr = [-1, 0, 1, 2], num = 0
0
arr = [-5, -2, 1, 4, 6], num = 5
6
הסבר: מספר השלישיות שסכומן קטן מ-5
arr = [10, 20, 30, 40], num = 100
4
הסבר: כל השלישיות במערך סכומן קטן מ-100
arr = [-10, -5, 0, 5, 10], num = -1
4
הסבר: השלישיות שסכומן קטן מ-(-1) הן השלישיות עם מספרים שליליים
קלט:
arr = [-2, 0, 1, 3], num = 2
הפלט המבוקש:
2