Subarray Sum Equals K

Problem

Count how many contiguous subarrays of nums sum to exactly k. Values may be negative.

Track the running prefix sum in a hash map of prefix counts: for each prefix p, the number of earlier prefixes equal to p - k gives the subarrays ending here. Runs in O(n) time.

Hint

A subarray between indices i and j sums to k exactly when prefix[j] - prefix[i] equals k.

Test cases

case 1

in: [[1,1,1],2]

expected: 2

case 2

in: [[1,2,3],3]

expected: 2

case 3

in: [[1,-1,0],0]

expected: 3

case 4

in: [[-1,-1,1],0]

expected: 1

case 5

in: [[],0]

expected: 0

case 6

in: [[0,0,0],0]

expected: 6

Starter codePython

def subarray_sum(nums, k):
    # Your code here
    pass

6 test cases · run your code against them in the editor