All problems

Subarray Sum Equals K

Medium · prefix sum

You are given a list of integers nums, which may contain negative numbers and zeros, and an integer k.

Return how many contiguous, non-empty parts of nums add up to exactly k.

Parts are told apart by where they start and end, not by their values. If the same values appear at two different places, each place counts separately. For example, in [0, 0] with k = 0 there are three parts: the first 0, the second 0 and both together.

If no part adds up to k, return 0.

Examples

Example 1

Input: nums = [1, 2, 3], k = 3

Output: 2

The parts [1, 2] and [3] both add up to 3.

Example 2

Input: nums = [1, -1, 0], k = 0

Output: 3

The parts [1, -1], [0] and [1, -1, 0] all add up to 0.

Example 3

Input: nums = [4, 5], k = 3

Output: 0

No part adds up to 3.

Constraints