Matching loads
MediumOnline Assessment
Count the consecutive segments that add up to a target.
A segment is a non-empty run of consecutive entries of values. Count every segment whose sum is exactly target. Segments are distinguished by their position, so equal-looking segments at different places are counted separately. Values may be negative or zero.
Input: values, a list of integers, and target, an integer.
Output: an integer, the number of matching segments. An empty list returns 0.
An O(n) approach exists; inputs are large enough that checking every segment will be too slow.
Example 1
- Input:
- [[1,-1,1],1]
- Output:
- 3
- Explanation
- Three segments sum to 1: the first [1], the whole list [1, -1, 1], and the last [1]. The other segments sum to 0 or -1.
Example 2
- Input:
- [[0,0,0],0]
- Output:
- 6
- Explanation
- Every segment sums to 0. A list of 3 has 3 + 2 + 1 = 6 non-empty segments, so the answer is 6.
Example 3
- Input:
- [[2,3,5,-5,5],5]
- Output:
- 5
- Explanation
- The five segments that sum to 5 are [2, 3], [5], [2, 3, 5, -5], [5, -5, 5] and the final [5].
Constraints
0 <= values.length <= 100,000-1,000 <= values[i] <= 1,000-100,000,000 <= target <= 100,000,000