Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals tok.
A subarray is a contiguous non-empty sequence of elements within an array.
Example 1:
Input: nums = [1,1,1], k = 2
Output: 2
Example 2:
Input: nums = [1,2,3], k = 3
Output: 2
Constraints:
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
Solutions
Solution 1: Hash Table + Prefix Sum
We define a hash table cnt to store the number of times the prefix sum of the array nums appears. Initially, we set the value of cnt[0] to 1, indicating that the prefix sum 0 appears once.
We traverse the array nums, calculate the prefix sum s, then add the value of cnt[s - k] to the answer, and increase the value of cnt[s] by 1.
After the traversal, we return the answer.
The time complexity is O(n), and the space complexity is O(n). Where n is the length of the array nums.