Subarray Sum Equals K¶

Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k.

Example 1¶

Input:nums = [1,1,1], k = 2
Output: 2

Solution¶

First let say we have a array

[1, 2, 3, 4]

Then we have a pre-array which contains the sum of the elements before.

[1, 3, 6, 10]

And we can find that the sum of sub-array [2, 3, 4] is equal to difference between 10 and 1

And now we can have a equation of sum of array from index j to index k

\[\sum_{i=j}^{k}array[i] = pre[k] - pre[j - 1] = target\]

Or

\[pre[k] - target = pre[j - 1]\]

And we can first store the value \(pre[j-1]\) and then find if any \(pre[k] - target\) is equal to the value we have before.

If so, then there is a sub-array with sum equals to target
Else, go to next value

from typing import List, Dict
def find_subarray(arr: List[int], target: int) -> int:
    pre = 0
    visited_map: Dict[int, int] = {0: 1}
    count = 0
    for i in range(len(arr)):
        pre += arr[i]
        # find if pre[k] - target exists
        if pre - target in visited_map:
            count  += visited_map[pre - target]
        # Set the current value to the map
        visited_map[pre] = visited_map.get(pre, 0) + 1

    return count

find_subarray([1, 1, 1], 2)

find_subarray([0,0,0,0,0,0,0,0,0,0], 0)