@dxpeng

you basically store the # of occurrence for each "prefix" sum of the array up to a given index.

For example,

if the array is [1 3 4 13]

our prefix sum dictionary will contain these elements at each index:

before start: {0:1} -> 0 sum would be the equivalent of an empty array

index 0: {0:1, 1:1} -> prefix sum up to and including index 0 is 1

index 1: {0:1, 1:1, 4:1} -> prefix sum up to and including index 1 is 4. If you're confused at this point, we're just storing the sum up to each index

index2: {0:1, 1:1, 4:1, 8:1} -> prefix sum up to index 2

index3: {0:1, 1:1, 4:1, 8:1, 21:1} prefix sum up to index 3 == 21

Now during the same iteration we can check if there is a prefix array we can discard to obtain our desired target of k. For example if k=7 in our example above when we arrive at index 2, our sum will be 8 but we can see that there is a prefix sum of 1 in the array according to our hashmap. Thus we can deduce that there is a contiguous subarray of sum 7 and this can be achieved by getting rid of the prefix array of sum of 1 in our current window. To visually illustrate:

our window at index2: [1 3 4]

prefix array with sum of 1: [1]

valid subarray with sum of k [1 3 4] - [1] = [3 4]

Don't pay attention to the syntax of the above equation as it's just to illustrate the concept of taking out the prefix array.

Another example would be if k = 17, then

window at index3 : [1 3 4 13] with a sum of 21. Since target is 17, we need to see if there's a prefix array that sums to 4.

According to our hashmap, at index1 we have a prefix array of sum of 4: [1 3]

thus: [1 3 4 13] - [1 3] = [4 13] which sums to 17