Member-only story
Prefix Sum (vs. sliding window)
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k. A subarray is a contiguous non-empty sequence of elements within an array.
If you’ve been following my blog post, you may recall that I covered the Sliding Window technique a while ago. Recently, while tackling some LeetCode problems, I encountered the question above, and at first glance, I thought I could apply the sliding window technique. To my surprise, my initial attempt failed. I then considered using the two-pointer approach, only to encounter further difficulties. After investing some hours attempting to solve the problem with these methods, I realized they were not yielding the desired results. After some research, I found a new technique called Prefix sum which can be used in tackling this problem.
Prefix Sum
Prefix sum, or cumulative sum, is keeping track of how the totals change as you move along a list or array. Let’s assume we have an array of numbers that we want to keep track of its sum as we iterate through each element.
In the diagram above, we start by setting the sum to 0. As we move through the numbers in the…
