# Subarray Sum Equals K

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

Output:
 2
```

**Note:**

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

## Analysis

**Approach 1 - Cumulative sum without space**

> Instead of considering all the startstart and endend points and then finding the sum for each subarray corresponding to those points, we can directly find the sum on the go while considering different endend points.
>
> Whenever the sumsum equals the required kk value, we can update the countcount value

```java
if (sum == k) count++;
```

**Approach 2 - Prefix Sum + Hash Table**

> If the cumulative sum(repreesnted by `sum[i]` for sum upto i-th index) upto two indices is the same, the sum of the elements lying in between those indices is zero.

`sum[i]` is prefix sum till i-th element

if `sum[j] − sum[i - 1] = k`, then update count.

Thus, storing prefix sum in hashmap, if (sum - k) found, then it means, we found a subarray with sum k.

Also, the hashmap keeps the count for the frequencies of the prefix sum (`sum i, No. of occurences of sum i`), so that it could add together to the total count of the subarray with sum k.

**Note**: *a **tricky** part is to **initialize** the hashmap with* `map.put(0, 1);`

Since actually the `sum` as hashmap key stored is `sum[0, j]`

and `sum[i, j] = sum[0, j] - sum[0, i - 1]`, therefore if the `sum[0, j]` itself is k, then we are checking if the map contains `0`

as key, so we have `map.put(0, 1);` to make sure the `count` will add one when it find `sum - k == 0`

Some explanation from discussion @y495711146:

```
/*
1. Hashmap<sum[0,i - 1], frequency>
2. sum[i, j] = sum[0, j] - sum[0, i - 1]    --> sum[0, i - 1] = sum[0, j] - sum[i, j]
       k           sum      hashmap-key     -->  hashmap-key  =  sum - k
3. now, we have k and sum.  
      As long as we can find a sum[0, i - 1], we then get a valid subarray
     which is as long as we have the hashmap-key,  we then get a valid subarray
4. Why don't map.put(sum[0, i - 1], 1) every time ?
      if all numbers are positive, this is fine
      if there exists negative number, there could be preSum frequency > 1
*/
```

<https://leetcode.com/problems/subarray-sum-equals-k/discuss/102106/Java-Solution-PreSum-%2B-HashMap>

**Another way** (straight-forward, preferred) of implementing it is just do a check outside of the hashmap containsKey(),

```java
if (sum == k) {
    count++;
}
```

in this way, we don't need to initialize hashmap with (0, 1).

See <https://www.geeksforgeeks.org/number-subarrays-sum-exactly-equal-k/>

## Solution

Cumulative sum - O(n^2) time, O(1) space (218 ms)

```java
public class Solution {
    public int subarraySum(int[] nums, int k) {
        int count = 0;
        for (int start = 0; start < nums.length; start++) {
            int sum=0;
            for (int end = start; end < nums.length; end++) {
                sum+=nums[end];
                if (sum == k)
                    count++;
            }
        }
        return count;
    }
}
```

Prefix Sum + Hash Table - O(n) time, O(n) space (37ms beats 40.49%)

```java
class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        int sum = 0;
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;

    }
}
```

Another implementation - Prefix Sum + Hash Table - O(n) time, O(n)

```java
class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums == null || nums.length == 0) return 0;
        int sum = 0;
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum == k) {
                count++;
            }
            if (map.containsKey(sum - k)) {
                count += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return count;

    }
}
```