The problem
A stretch is one or more neighbouring values of a, like a[2], a[3], a[4]. Count the stretches whose values add up to exactly k. Values can be negative.
count_sums([1, 1, 1], 2) # 2: [1, 1] twice
count_sums([1, 2, 3], 3) # 2: [1, 2] and [3]
count_sums([1, -1, 0], 0) # 3: [1, -1], [0], [1, -1, 0]
Limits
- Up to 200,000 values. There are about n²/2 stretches, so you cannot try them all.
Builds on HASH-6 Counting and grouping.
Continue on a laptop
Practice runs Python in the browser and needs a keyboard and a wider screen. Read the problem and open hints here, then write your solution on a laptop. Progress is saved per browser for now, so hints opened here stay on this device.
Need a hint?0 of 3 opened
- Hint 1Nudge
- Hint 2Approach Open hint 1 first
- Hint 3Pseudocode Open hint 2 first
- Worked solutionlast resort Opens after all 3 hints
Ctrl + Enter runs the tests. Tab indents; press Esc, then Tab, to leave the editor.
8 tests, not run yet
| # | Test | Result | Reads · time |
|---|---|---|---|
| 1 | Small | Not run | |
| 2 | Different lengths | Not run | |
| 3 | Negative values | Not run | |
| 4 | Zeros | Not run | |
| 5 | Empty | Not run | |
| 6 | Mixed | Not run | |
| 7 | Whole list only | Not run | |
| 8 | 200,000 values | Not run |