> For the complete documentation index, see [llms.txt](https://docs-57.gitbook.io/data-structure-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://docs-57.gitbook.io/data-structure-and-algorithms/problems/array/subarray-sum-equals-k.md).

# 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)`


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs-57.gitbook.io/data-structure-and-algorithms/problems/array/subarray-sum-equals-k.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.