# Subarray Sum Equals K
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/subarray-sum-equals-k)
Canonical: https://scaleengineer.com/dsa/problems/subarray-sum-equals-k
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, Hash Table
**Companies:** [AMD](https://scaleengineer.com/companies/amd), [ByteDance](https://scaleengineer.com/companies/bytedance), [Capgemini](https://scaleengineer.com/companies/capgemini), [Cisco](https://scaleengineer.com/companies/cisco), [Flipkart](https://scaleengineer.com/companies/flipkart), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [IBM](https://scaleengineer.com/companies/ibm), [Infosys](https://scaleengineer.com/companies/infosys), [J.P. Morgan](https://scaleengineer.com/companies/j.p.-morgan), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [Nagarro](https://scaleengineer.com/companies/nagarro), [PayPal](https://scaleengineer.com/companies/paypal), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Tinkoff](https://scaleengineer.com/companies/tinkoff), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Yandex](https://scaleengineer.com/companies/yandex), [tcs](https://scaleengineer.com/companies/tcs), [Tesla](https://scaleengineer.com/companies/tesla), [Snap](https://scaleengineer.com/companies/snap), [Swiggy](https://scaleengineer.com/companies/swiggy), [Disney](https://scaleengineer.com/companies/disney), [Ripple](https://scaleengineer.com/companies/ripple), [Apollo.io](https://scaleengineer.com/companies/apollo.io), [Scale AI](https://scaleengineer.com/companies/scale-ai), [Quora](https://scaleengineer.com/companies/quora)
---
## Problem
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:**

**Input:** nums = [1,1,1], k = 2
**Output:** 2

**Example 2:**

**Input:** nums = [1,2,3], k = 3
**Output:** 2

**Constraints:**

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

# Approaches
## Brute Force with Cumulative Sum
The most straightforward approach is to consider every possible subarray, calculate its sum, and check if the sum equals `k`. We can optimize the sum calculation by iterating through all possible start points and for each start point, extending the subarray to the right while keeping a running sum.
**Time:** O(n^2), where n is the length of `nums`. The two nested loops lead to a quadratic runtime, which is too slow for the given constraints. · **Space:** O(1), as we only use a constant amount of extra space for variables like `count` and `currentSum`.
**Pros:** Simple to understand and implement.; Requires no extra space (O(1) space complexity).
**Cons:** Inefficient time complexity, leading to "Time Limit Exceeded" on larger test cases as per the problem constraints.
### Explanation
This approach iterates through all possible starting points of a subarray. For each starting point, it iterates through all possible ending points, effectively generating every contiguous subarray. A running sum is maintained for the current subarray, and if this sum equals `k`, a counter is incremented.

```java
public int subarraySum(int[] nums, int k) {
    int count = 0;
    for (int start = 0; start < nums.length; start++) {
        int currentSum = 0;
        for (int end = start; end < nums.length; end++) {
            currentSum += nums[end];
            if (currentSum == k) {
                count++;
            }
        }
    }
    return count;
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use an outer loop with index `start` from 0 to `n-1` to select the starting element of the subarray.
- Inside the outer loop, initialize a `currentSum` to 0.
- Use an inner loop with index `end` from `start` to `n-1`. This loop defines the end of the subarray.
- In each step of the inner loop, add `nums[end]` to `currentSum`. This `currentSum` represents the sum of the subarray `nums[start...end]`.
- If `currentSum` is equal to `k`, increment `count`.
- After both loops complete, return `count`.

## Prefix Sum with Hash Map
This is the most efficient approach, utilizing a hash map to store prefix sums and their frequencies. The core idea is that if the cumulative sum up to two indices `i` and `j` (where `i < j`) is `sum_i` and `sum_j` respectively, then the sum of the subarray between `i` and `j` is `sum_j - sum_i`. We are looking for subarrays where `sum_j - sum_i = k`, which can be rewritten as `sum_i = sum_j - k`.
**Time:** O(n), where n is the length of `nums`. We iterate through the array only once. Hash map operations (put and get) take constant time on average. · **Space:** O(n), as the hash map can store up to `n` distinct prefix sums in the worst case where all prefix sums are unique.
**Pros:** Highly efficient with linear time complexity.; Solves the problem within the given constraints.
**Cons:** Requires extra space for the hash map, which can be up to O(n) in the worst case.; The logic is slightly more complex to grasp compared to the brute-force method.
### Explanation
By iterating through the array, we can maintain the current prefix sum. For each element, we calculate the `currentSum`. Then, we check if `currentSum - k` exists in our hash map. If it does, it means there's a previous prefix sum that, when subtracted from the `currentSum`, gives `k`. The number of times `currentSum - k` has occurred corresponds to the number of new subarrays ending at the current position with a sum of `k`. We then update the map with the `currentSum`.

```java
import java.util.HashMap;
import java.util.Map;

public int subarraySum(int[] nums, int k) {
    int count = 0;
    int currentSum = 0;
    Map<Integer, Integer> prefixSumMap = new HashMap<>();
    // Base case: a prefix sum of 0 has occurred once (the empty prefix)
    prefixSumMap.put(0, 1);

    for (int num : nums) {
        currentSum += num;
        // Check if a subarray ending here sums to k
        // This is equivalent to finding a previous prefix sum `p` such that `currentSum - p = k`
        // or `p = currentSum - k`
        if (prefixSumMap.containsKey(currentSum - k)) {
            count += prefixSumMap.get(currentSum - k);
        }
        // Add the current prefix sum to the map
        prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1);
    }
    return count;
}
```
### Algorithm
- Initialize `count = 0` and `currentSum = 0`.
- Create a hash map `prefixSumMap` to store the frequency of each prefix sum encountered.
- Put an initial entry `(0, 1)` into the map. This handles cases where a subarray starting from index 0 sums to `k`.
- Iterate through the `nums` array. For each number `num`:
    - Add `num` to `currentSum`.
    - Check if `prefixSumMap` contains the key `currentSum - k`. If it does, it means there are `prefixSumMap.get(currentSum - k)` subarrays ending at the current position that sum to `k`. Add this frequency to `count`.
    - Update the frequency of the `currentSum` in the `prefixSumMap`. Increment its count by 1.

# Solutions
### Java

```java
class Solution {
public
  int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> counter = new HashMap<>();
    counter.put(0, 1);
    int ans = 0, s = 0;
    for (int num : nums) {
      s += num;
      ans += counter.getOrDefault(s - k, 0);
      counter.put(s, counter.getOrDefault(s, 0) + 1);
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int subarraySum(vector<int> &nums, int k) {
    unordered_map<int, int> counter;
    counter[0] = 1;
    int ans = 0, s = 0;
    for (int &num : nums) {
      s += num;
      ans += counter[s - k];
      ++counter[s];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    # not matter if the same num like [1,1] dp [ s ] += 1 return ans ############# class Solution : # over time limit, not fast enough def subarraySum ( self , nums : List [ int ], k : int ) -> int : count = 0 # sum value from 1 to i-th element sum_arr = [ 0 ] * ( len ( nums ) + 1 ) # cached sum for i in range ( 1 , len ( nums ) + 1 ): sum_arr [ i ] = sum_arr [ i - 1 ] + nums [ i - 1 ] for start in range ( len ( nums )): for end in range ( start + 1 , len ( nums ) + 1 ): if sum_arr [ end ] - sum_arr [ start ] == k : count += 1 return count
    def subarraySum(self, nums: List[int], k: int) -> int: dp = Counter({0: 1}) ans = s = 0 for num in nums: s += num ans += dp[s - k]

```