Learn to resolve the Subarray Sum Equals K problems by using Brute force, Sliding window, and Hash table algorithms

### Problem 1

- Given an unsorted array of non-negative integers
`a[n]`

and an integer`k`

- Find a continuous subarray whose sum equals to
`k`

### Example 1.1

Input: a = [4, 0, 11, 6, 1, 7] and k = 8

Output: [1, 7]

### Approach 1.1: Brute Force

Consider the sum of every continuous subarray

Return the first subarray when its sum equals to

`k`

```
```

Time complexity: O(n

^{2}) as with each element in the given array, you iterate over the remaining elements to calculate the sum of possible subarraysSpace complexity: O(1)

### Approach 1.2: Sliding Window

Find the sliding window sum, say

`ws`

, in the index range`[i, j]`

of the given array`a[n]`

, that equals`k`

by increasing`j`

continuously from`i`

to`n-1`

Return the result as

`ws`

as soon as it equals`k`

, otherwise, reduce`ws`

and increase`i`

```
```

Time complexity: O(n)

Space complexity: O(1)

### Problem 2

Given an unsorted array of integers

`a[n]`

and an integer`k`

Find the total number of continuous subarrays whose sum equals to

`k`

### Example 2.1

Input: a = [-4, 12, -11, 6, 1, 7], k = 8

Output: 3

Explanation: [-4, 12], [12, -11, 6, 1], [1, 7] are 3 subarrays have sum equals to 8

### Approach 2.1: Hash table

Say c

_{i}, c_{j}is the cumulative sum at index`i`

and`j`

in the given array`a[n]`

Elements from

`i`

to`j`

will form a subarray that satify the constraint if c_{j}- k = c_{i}∀ 0 <= i < j < nUse a hash table

`h`

with key = c_{i}∀ 0 <= i < n, value = count(c_{i}) in`h`

The final result is count(h.getValueByKey(c

_{i}- k))

```
```

Time complexity: O(n) as the given array is traversed through only once

Space complexity: O(n) as the hash table can hold up to

`n`

elements