AlgoViz
HomeArrays & Hashing

Count subarrays with given sum

Medium

Count prefix sums you have already seen

Problem

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

In simple words

Keep a map of how often each running sum appears; each time current-minus-k was seen, add those counts.

The idea

A subarray sums to k exactly when the current prefix minus some earlier prefix equals k, so keep a count of every prefix sum seen and add the count of prefix - k at each step. Counting occurrences rather than storing indices is what makes it O(n).

The trick

  • Seed the map with {0: 1} so subarrays starting at index 0 are counted.
  • Add the lookup before inserting the current prefix, to avoid matching yourself.
  • Works with negatives, unlike a sliding window.
1
2
3
-3
1
1
1
0
1
2
3
4
5
6
target3

Step 1 of 30. Brute force: add up every subarray, count those summing to 3. Values: 1, 2, 3, -3, 1, 1, 1. target 3.

1/30
Brute force
timeO(n²)spaceO(1)

Sum every subarray.

1// add up every subarray, count the ones equal to k2for (let i = 0; i < n; i++) {3  let sum = 0;4  for (let j = i; j < n; j++) {5    sum += nums[j];6    if (sum === k) count++;7  }8}

Input

array
[1, 2, 3, -3, 1, 1, 1]

Memory

target
3

Output

count
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 1, 1], k = 2
Output:
2
Explanation:
Two windows [1,1] each sum to 2.

Example 2

Input:
nums = [1, 2, 3], k = 3
Output:
2
Explanation:
[3] and [1,2] both total 3.

Example 3

Input:
nums = [0, 0, 0], k = 0
Output:
6
Explanation:
Every window of 0s sums to 0.

Constraints

  • 1 <= nums.length <= 10^5
  • -1000 <= nums[i] <= 1000
  • -10^7 <= k <= 10^7

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.