Subarray with Specific Sum

Given an unsorted array of nonnegative integers, find a continuous subarray which adds to a given number.

Examples:

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Output: Sum found between indexes 2 and 4

Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Output: Sum found between indexes 1 and 4

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found

There may be more than one subarrays with sum as the given sum. Print first such subarray.

Solution

1. Take two indices start and end denoting the starting and ending index.,which initially point to first element A[0] and a variable sum which stored the current sum (=A[0]).
2. Now increase end until and unless sum becomes greater than required sum S. This is done because we cannot find S in a subarray whose maximum sum is less than S.
3. Now once sum becomes greater than S, we have chance to find a subarray with ending point as end. Therefore we can increase start until it is not greater than sum . Once it becomes smaller ,we are back to step 2. Now if no subarray exists for which sum is S, start will be eventually equal to end, so now the new problem will be array starting at start+1 and ending at end+1.

Code

int subarray_sum(int array[], int N, int S, int &start, int &end){

start = end = 0;
while(end < N && start < N){

while(current_sum < sum && end < N)

current_sum += array[end++];

while(current_sum > sum && start < N){

current_sum -= array[start++];

if(current_sum == sum)

return 1;

}

}
return 0;

}

Complexity

• Time : O(N)
• Space : O(1)