# Subarray sum equals k

### Problem

<https://leetcode.com/problems/subarray-sum-equals-k/description/>

<figure><img src="https://1388126071-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MVQ7Ie-PZpN_8yApX0-%2Fuploads%2Fs83Q4wizXhXjLIxX4GUJ%2Fimage.png?alt=media&#x26;token=91aa3ab2-273b-4225-b167-d66335fea335" alt=""><figcaption></figcaption></figure>

### Understanding of problem

### Solution&#x20;

```java
class Solution {
    public int subarraySum(int[] nums, int k) {
        // n -> length of array "n"
        // Time complexity: O(n) 
        // It is one pass
        // Space complexity: O(n) (for Hashmap)


        // Keeps track of {sum till index: number of times it occurred}
        Map<Integer, Integer> map = new HashMap<>();
        // When we encounter "k" in the range from [0, i],
        // It is also a valid subarray

        // Since we are considering complements,
        // If the complement of [0,i] == 0, then the subarray
        // [0, i] should be counted. It is an edge case, so we add
        // map.put(0,1), to cover that case
        map.put(0,1); 

        int prefix = 0, count = 0;

        for(int i=0;i<nums.length;i++) {
            prefix += nums[i]; // Prefix sum, i.e sum so far
            int complement = prefix - k;
            // Checking if the complement is present in the map, 
            // helps in understanding if a 
            // particular range in array contains sum == "k"
            // If complement is present in the map, then increment the count
            count += map.getOrDefault(complement, 0);

            // Store the prefix sum with the number of times it occurred
            // It might not make sense with only positive integers,
            // But when you have negative numbers, then a particular prefix might
            // be occurring more than once
            map.put(prefix, map.getOrDefault(prefix,0)+1);
        }
        return count;
    }
}
```

### Reference Submissions

* <https://leetcode.com/problems/subarray-sum-equals-k/submissions/913837394/>
* <https://leetcode.com/problems/subarray-sum-equals-k/submissions/734216658/>