Continuous Subarray Sum to Target Value

Continuous Subarray Sum to Target Value

Given an array of integers, find a continuous subarray which sums to a given number, d return the index pair.

Example: {3, 1, 5, 6, 2, 5, 3}, target sum is 12, should return {1, 3}, which means 1+5+6=12

Analysis

If the array only contains non-negative numbers, it can be solved using sliding window. However, if it can contain negative values, then sliding window can fail.

The most naive method is to start from each element and add till the end to check if there is a continous subarray starting from this element that can sum to the given value. The time complexity is O(N^2).

However, it is possible to improve this by using a map. The idea is to store the sum from index 0 to i as the key. We can denote it as sum[i]. In this way, when given a new number, we only need to check if sum[j] - target exists in the map. If it exist in the map, it means that num[i+1] to num[j] sums up to target.

Read full article from Continuous Subarray Sum to Target Value