Subarray Sum Equals K

---

Subarray Sum Equals K: 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 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

---

Try this Problem on your own or check similar problems:

1. Continuous Subarray Sum
2. Subarray Product Less Than K
3. Subarray Sums Divisible by K
4. Minimum Operations to Reduce X to Zero

Solution:

Java

public int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, 1);
    int count = 0, sum = 0;

    for(int i = 0; i < nums.length; ++i){
        sum += nums[i];
        count += map.getOrDefault(sum - k, 0);
        map.put(sum, map.getOrDefault(sum, 0) + 1);
    }

    return count;
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
  const map = new Map();
  map.set(0, 1);
  let count = 0;
  let sum = 0;

  for (let i = 0; i < nums.length; ++i) {
    sum += nums[i];
    count += map.get(sum - k) || 0;
    map.set(sum, (map.get(sum) || 0) + 1);
  }

  return count;
};

Python

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        map = {}
        map[0] = 1
        count = 0
        sum = 0

        for num in nums:
            sum += num
            count += map.get(sum - k, 0)
            map[sum] = map.get(sum, 0) + 1

        return count

C++

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        map[0] = 1;
        int count = 0;
        int sum = 0;

        for (int num : nums) {
            sum += num;
            count += map[sum - k];
            map[sum]++;
        }

        return count;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(n)

---

Explanation:

The problem is based on prefix sum Range Query Sum Immutable rule, if we have difference k between sum ending at index i and sum ending at index j we know that elements between those indices form a subarray with sum k. We use the map to count number of times prefixSum appears (it can appear more than once when hit index i) and increase the count accordingly. The space and time complexity are linear and proportional to the input array size. One thing to note that at beginning we have prefixSum 0 since we can have first few numbers forming a prefixsum k when we search in the map for k-k=0 we should find 0 prefixSum at least once for the first subarray with sum k.