Subarray Sum Equals K

01 · Question

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

02 · Analysis

A subarray sum equals k when the current prefix minus an earlier prefix equals k. Store frequencies of earlier prefix sums, initialized with {0:1}. Query current-k before inserting current to exclude an empty range, especially for k=0. Repeated prefixes represent different starts and must all count. Expected O(n) time, O(n) auxiliary space; signed values are allowed.

03 · Solution

Reference solution

1def subarraySum(nums: List[int], k: int) -> int:
2    count = {0: 1}
3    pref = 0
4    res = 0
5
6    for x in nums:
7        pref += x
8        need = pref - k
9        res += count.get(need, 0)
10        count[pref] = count.get(pref, 0) + 1
11
12    return res

Range Sum Query - Immutable

Find Pivot Index