CodePark/ problems / Count Subarrays With Sum K
START PRACTICINGPRACTICE
Coding problem · Data structures and algorithms › Hash maps and sets

Count Subarrays With Sum K

mediumabout 25 minutes in an interview

A subarray is a run of one or more neighbouring items in an array. For [2, 1, -1] the subarrays are [2], [1], [-1], [2, 1], [1, -1] and [2, 1, -1].

Write countSubarraysWithSum(nums, k) that returns how many subarrays of nums add up to exactly k.

  • Numbers can be negative, zero or positive. The same goes for k.
  • Subarrays at different positions count separately, even if they hold the same values.
  • An empty nums has no subarrays: return 0.
  • nums can have up to 100,000 items, so checking every start and end is too slow.
Input: nums = [2, 1, -1, 3], k = 3 Output: 3[2, 1], [1, -1, 3] and [3].
Input: nums = [1, 1, 1], k = 2 Output: 2[1, 1] starting at index 0, and [1, 1] starting at index 1.
Input: nums = [0, 0, 0], k = 0 Output: 6Every one of the 6 subarrays sums to 0.