<p>Given an array of integers <code>nums</code> and an integer <code>k</code>, return <em>the total number of subarrays whose sum equals to</em> <code>k</code>.</p>

<p>A subarray is a contiguous <strong>non-empty</strong> sequence of elements within an array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<pre><strong>Input:</strong> nums = [1,1,1], k = 2
<strong>Output:</strong> 2
</pre><p><strong class="example">Example 2:</strong></p>
<pre><strong>Input:</strong> nums = [1,2,3], k = 3
<strong>Output:</strong> 2
</pre>
<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>-1000 &lt;= nums[i] &lt;= 1000</code></li>
	<li><code>-10<sup>7</sup> &lt;= k &lt;= 10<sup>7</sup></code></li>
</ul>

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # check how many times prefix_sum[i]-k has been seen before in the array, using a hash map to store the frequency of each prefix sum. 
        """
        iterate over the array and calculate the prefix sum at each step. 
        for each prefix sum, check how many times prefix_sum[i]-k has been seen before. 
        store the prefix sums in a hash map with their frequency to track how many times each sum has been encountered. 
        return the total count of subarrays with sum equal to k. 
        """
        remainder_map = {0:1}
        prefix_sum = 0
        output = 0
        count = 0
        for i,num in enumerate(nums):
            prefix_sum += num
            if prefix_sum - k in remainder_map.keys():
                count += remainder_map[prefix_sum-k]
            if prefix_sum in remainder_map.keys():
                remainder_map[prefix_sum] += 1
            else:
                remainder_map[prefix_sum] = 1
        return count
19400