# 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:

# The solution

Here the dictionary is used to store the memo, as lookup can happen (on average) O(n).

# Conclusion

This is a really important theoretical tool for your programming toolbox, and is one that is often used for those people who have LeetCode problems to solve.

stevecurtis.me

Get the Medium app