# Subarray Sum Equals K

{% hint style="info" %}
Array, Hash Table
{% endhint %}

Given an array of integers `nums` and an integer `k`, return *the total number of subarrays whose sum equals to* `k`.

A subarray is a contiguous **non-empty** sequence of elements within an array.

 

**Example 1:**

<pre><code><strong>Input: nums = [1,1,1], k = 2
</strong><strong>Output: 2
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: nums = [1,2,3], k = 3
</strong><strong>Output: 2
</strong></code></pre>

&#x20;

**Constraints:**

* `1 <= nums.length <= 2 * 104`
* `-1000 <= nums[i] <= 1000`
* `-107 <= k <= 107`

### Solutions

#### Approach - Brute Force Technique

**Steps**

1. **Initialize Counter**: The algorithm starts by initializing a counter `count` to 0. This will keep track of the number of subarrays that sum to `k`.
2. **Iterate Over Array**: The algorithm then enters a nested loop that iterates over each possible subarray in `nums`.
   * **Calculate Subarray Sum**: For each subarray, the algorithm calculates the sum of the elements in the subarray.
   * **Check for Desired Sum**: If the sum of the elements in the subarray equals `k`, the algorithm increments `count`.
3. **Return Result**: After the loops, the algorithm returns `count`, which is the total number of continuous subarrays whose sum equals to `k`.

```csharp
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;
    }
}
```

> Complexity

* **Time complexity**: `O(N^2)`
* **Space complexity**: `O(1)`

#### Approach - Hash Table Technique

**Steps**

1. **Initialize Variables**: The algorithm starts by initializing a dictionary `prefix` to keep track of cumulative sums and their counts, an integer `sum` to keep track of the cumulative sum, and an integer `ret` to keep track of the number of subarrays that sum to `k`.
2. **Handle Base Case**: The algorithm adds an entry to the `prefix` dictionary for a sum of zero with a count of one. This represents the sum of no elements.
3. **Iterate Over Array**: The algorithm then enters a loop that iterates over each element in the input array `nums`.
   * **Update Cumulative Sum**: For each element, the algorithm adds the element’s value to `sum`.
   * **Check for Subarray Sum**: The algorithm calculates the value `find` as the difference between the current cumulative sum and `k`. If `find` is in the `prefix` dictionary, it means that there is a subarray ending at the current index with a sum of `k`. The algorithm increments `ret` by the count of `find` in `prefix`.
   * **Update Prefix Dictionary**: The algorithm then checks if the current cumulative sum is in the `prefix` dictionary. If it is, the count is incremented; otherwise, a new entry is added with a count of one.
4. **Return Result**: After the loop, the algorithm returns `ret`, which is the total number of continuous subarrays whose sum equals to `k`.

```csharp
public class Solution {
    public int SubarraySum(int[] nums, int k) {

        Dictionary<int, int> prefix = new Dictionary<int, int>();
        int sum = 0;
        int ret = 0;
        prefix[0] = 1; // we always have 1 sum of zero, which is sum of none.
        for (int i = 0; i < nums.Length; i++)
        {
            sum += nums[i];

            int find = sum - k;
            if (prefix.ContainsKey(find))
            {
                ret += prefix[find];
            }
            if (prefix.ContainsKey(sum))
            {
                prefix[sum]++;
               
            }
            else
            {
                
                prefix.Add(sum, 1);
            }
            
        }
        return ret; 
    }
}
```

> Complexity

* **Time complexity**: `O(N)`
* **Space complexity**: `O(N)`