Understanding Prefix Sum for LeetCode Problems

This can be hard

The background

There are number of prefix sum problems on LeetCode, and they tend to either be Medium or Hard problems. Is there a way this can be reasonably explained and coded?

Let us have a go!

The problem

Given an array of Int nums, and an integer k calculate the number of continuous subarrays whose sum equals the integer k.

Continuous means that there cannot be a gap in the subarray.

The explanation

It is possible to create a memo using a dictionary to make our answer as efficient as possible (since a dictionary can be accessed in O(n)).

So the count is incremented if we have visited the prefixSum — 3 (and natually this must have came before the current num we are visiting, in continuous order).

So here is an example where k = 3 and nums is [1,2,3,4,2,1] which gives the result as 3, represented as three blue arrows here: