Subarray Sum Equals K

mediumSave

ArrayHash TablePrefix Sum

Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k.

Example 1

Input

[
  1,
  1,
  1,
  2,
  1,
  2
]

Output

Explanation. There are three subarrays whose sums are equal to 2: [1, 1], [2], [2].

Example 2

Input

[
  1,
  2,
  3
]

Output

Explanation. There are two subarrays whose sums are equal to 3: [1, 2], [3].

Example 3

Input

[
  1,
  -1,
  0
]

Output

Explanation. There is one subarray whose sum is equal to 0: [1, -1, 0].

Follow-up: Can you solve the problem in O(n) time complexity?

Constraints:

The length of the array `nums` is between 1 and 20,000. Each element in the array is an integer that could range from -1000 to 1000. The integer `k` will not exceed `10^4` in absolute value.

Views: 3