Subarray Sum Equals K

Subarray Sum Equals K: the approach in brief

The problem

Given an integer array nums and an integer k, consider every non-empty subarray of nums. A subarray is a contiguous sequence of one or more elements, and its sum is the total of its elements.

Pattern

Subarray Sum Equals K is a Array/Matrix Manipulation Patterns problem, in the Hashing - Frequency Map / Counting subpattern. The pattern covers in-place operations, hashing, prefix sums, spiral traversal, and cyclic sort

Approach outline

1. Scan the array from left to right while maintaining the sum of all elements seen so far.
2. For a current cumulative sum `s`, an earlier cumulative sum of `s - k` marks a contiguous range ending at the current position whose sum is `k`.
3. Record the frequency of every cumulative sum, because the same sum can occur at multiple earlier positions.

Complexity

The reference solution runs in O(n) average time time and O(n) space.