#204MediumPrefix Sums & Difference Arrays· Prefix Sums with a Hash Map

Subarray Sum Equals Budget

A finance team exports a ledger as an array `nums` of amounts: positive for income, negative for expenses. An auditor wants to know how many **contiguous stretches** of the ledger add up to exactly a given `budget`. Count the non-empty contiguous subarrays of `nums` whose sum equals `budget`. Stretches at different positions count separately even if they hold the same values. Because amounts can be negative, a sliding window that only grows or shrinks does not work.

Input format

`nums`: the ledger amounts. `budget`: the target sum.

Output format

The number of contiguous subarrays whose sum equals `budget`.

Examples

Input: nums = [1, 1, 1], budget = 2

Output: 2

The stretches [1, 1] at positions 0-1 and 1-2 both add up to 2, so the answer is 2.

Input: nums = [3, 4, -7, 1, 3, 3, 1, -4], budget = 7

Output: 4

Four stretches add up to 7: [3, 4] (positions 0-1), [3, 4, -7, 1, 3, 3] (positions 0-5), [1, 3, 3] (positions 3-5) and [3, 3, 1] (positions 4-6).

Input: nums = [0, 0, 0], budget = 0

Output: 6

Every non-empty stretch sums to 0: three of length 1, two of length 2 and one of length 3, so 6.

Constraints

1 <= nums.length <= 2 * 10^4
-1000 <= nums[i] <= 1000
-10^7 <= budget <= 10^7

#prefix-sums
#hash-table
#subarray
#counting