Understanding Prefix Sum for LeetCode Problems
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!
Given an array of Int
nums, and an integer
k calculate the number of continuous subarrays whose sum equals the integer
Continuous means that there cannot be a gap in the subarray.
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:
Here the dictionary is used to store the memo, as lookup can happen (on average) O(n).
You can download the repo from here!
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.
If you’ve any questions, comments or suggestions please hit me up on Twitter