Subarray Sum Equals K Medium 0 attempts
LeetCode ↗

Subarray Sum Equals K

Medium ArrayTwo Pointers LeetCode

You're given an array of integers nums and an integer k. Count how many contiguous, non-empty slices of the array (subarrays) have elements that add up to exactly k.

Input Format
Implement subarraySum(nums, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

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

Example 2

Input
nums = [1,-1,0]
k = 0
Output
3
Constraints
  • 1 <= nums.length <= 2 * 10^4
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7
Test Cases (2)
Case 1
Args: [[1,1,1],2] Expected: 2
Case 2
Args: [[1,-1,0],0] Expected: 3
Topics
ArrayTwo Pointers

Use a hash map to store prefix sums and their frequencies. At each index, check if currentSum - k exists in the map — if so, those many subarrays ending here sum to k.

javascript
function subarraySum(nums, k) {
  const prefixCount = new Map([[0, 1]]);
  let sum = 0, count = 0;

  for (const num of nums) {
    sum += num;
    if (prefixCount.has(sum - k)) {
      count += prefixCount.get(sum - k);
    }
    prefixCount.set(sum, (prefixCount.get(sum) || 0) + 1);
  }

  return count;
}

Time: O(n) Space: O(n)

Saved in this browser only. Private to you.

JavaScript