## Description

Given an array of integers and an integer **k**, you need to find the total number of continuous subarrays whose sum equals to **k**.

## Example

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

**Note:**

- The length of the array is in range [1, 20,000].
- The range of numbers in the array is [-1000, 1000] and the range of the integer
**k**is [-1e7, 1e7].

## Solution 1: brute force

**Time complexity: O(n^3)**

Try all the the possibilities for `startIndex`

and `endIndex`

of subarray, and check the sum to see if equals `k`

`startIndex`

:`i = 0 ... n`

`endIndex`

:`j = i ... n`

- sum and check: another loop

1 | let subarraySum = function(nums, k) { |

## Solution 2: optimize using `prefix sum`

**Time complexity: O(n^2)**

__prefixSum array:__**Spcae Complexity: O(n)**For the inner most loop, there are duplicate work for the addition to get

`sum(i, j)`

. In fact, we can process it beforehand, getting an prefix sum array; Then`sum(i,j)`

will be`prefixSum[j]-prefixSum[i-1]`

, using`O(1)`

time__do summation in the fly:__**Spcae Complexity: O(1)**

1 | // approach #1: prefixSum array |

## Solution 3: optimize using `HashMap`

**Time complexity: O(n)**

**Space complexity: O(1)**

Based on Solution 2, we can get the subarray sum in O(n), but still the overall time complexity is `O(n^2)`

, that’s because we need to try all the possibilities of the `startIndex`

and `endIndex`

of subarray.

For each `startIndex: i`

, the reason we need to iterate `endIndex: j`

is that we want to find all the possible pair to make the subarray sum equals k.

If we change a direction to think about it, why not directly find all the the `prefixSum[i']`

, making `prefixSum[j] - prefixSum[i'] = k`

, and then we count all the possible `i'`

. Thus, we need a memory to let know who will be the counterpart for the current `prefixSum[j]`

. That’s `hashmap`

~

1 | let subarraySum = function(nums, k) { |