Back to ArraysSubarray Sum Equals K
Medium

Subarray Sum Equals K

MediumMust DoHashingPrefix Sum

Given an array of integers (which may include negative numbers) and a target k, count how many contiguous subarrays sum to exactly k.

Examples

Example 1

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

Explanation: Two subarrays sum to 2: [1,1] (indices 0-1) and [1,1] (indices 1-2).

Example 2

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

Explanation: [1,2] and [3] both sum to 3.

Example 3

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

Explanation: With a negative number present, [1,-1], [1,-1,0], and [0] all sum to 0 — a plain sliding window would fail here because shrinking the window on a negative number can increase the sum instead of decreasing it.

Constraints

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

Loading editor…

Code execution is coming soon.