Given an array of integers and an integerk, you need to find the total number of continuous subarrays whose sum equals tok.Example 1:Input:nums = [1,1,1], k = 2Output:2

The brute force approaching would be checking each substrings fo the input leading to O(n^2) time complexity. To improve it, we may observe that, taking `arr=[1,2,3]`

as an example, we would exhaust `1,1+2,1+2+3,2,2+3,3`

, where repeated computations happen. If we store the pre-sums along our scanning, we would be able to solve it with one-pass.

#### Logic

As shown above, we maintain an array `sum`

to record the sum of `arr[0...j]`

. Our strategy is to scan the array, count the pre-sums of `arr[0...j]`

and find the number of qualified substrings `arr[i...j]`

that ends with `arr[j]`

.

To find the substrings `arr[i...j]`

that are qualified, i.e., `sum[i...j]==target`

, we need to find `i`

that `sum[0...i]==sum[0...j]-target`

. To achieve this in O(1), we use one hashmap `dic`

to record the frequencies of each pre-sum.

#### Code

```
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
dic = collections.defaultdict(int)
dic[0] = 1
total = ret = 0
for e in nums:
total += e
ret += dic[total - k]
dic[total] += 1
return ret
```