A seesaw counter reads a list of pulls. For a stretch pulls[i..j] it computes the seesaw tally: the first pull of the stretch is added, the second subtracted, the third added, and so on:
pulls[i] - pulls[i+1] + pulls[i+2] - ... up to pulls[j].
Return how many non-empty stretches (i, j) with i <= j have a seesaw tally of exactly target.
Examples
Input: pulls = [5, 2, 3, 1], target = 3
Output: 2
Explanation: [5, 2] gives 5 - 2 = 3 and [3] gives 3. [5, 2, 3, 1] gives 5 - 2 + 3 - 1 = 5.
Input: pulls = [4, 4, 4], target = 4
Output: 4
Explanation: the three single pulls, and [4, 4, 4] with 4 - 4 + 4 = 4.
Input: pulls = [], target = 0
Output: 0
Constraints
0 <= len(pulls) <= 10**5-10**4 <= pulls[i] <= 10**4,-10**9 <= target <= 10**9- Target complexity: O(n). Recomputing the tally for every stretch is far too slow for the largest tests.
Goals
- Express an alternating total through one globally signed running total
- Notice that the start position's parity flips the sign
- Keep one dictionary per parity of the start