Subarray with a given sum – sliding window technique

Problem statement – Given an unordered array of input. Find a continuous subarray which adds to the given sum.

Example

Input array (arr) – {2,3,2,4,5,1,7,6,3,7}

Given sum (reqdSum) – 10

The sum is found between index 3 and 5

Return 1 if the subarray is found and return 0 if not found. Also print the indexes if found.

Sliding window technique for subarray with given sum

Approach:

>> Start accumulating the sum of array elements from the beginning in currSum.

>> Keep track of starting index of the subarray for which we are finding currSum. Initially we start with start = 0.

>> After each addition,compare currSum to the reqd sum.

>>> If equal, then the job is done. Just return the start index and the current element index.

>>> If less, then we can still try adding more numbers. So, do nothing. Element will be added in next iteration.

>>> If more, we have exceeded the reqdSum. Now we should remove the elements from the sub array (starting from the beginning. Index will be given by ‘start’). Remove the elements from the beginning of the subarray as far as the currSum is greater than required sum. We just have to subtract the elements in the beginning from the currSum. While removing each element, increment start so as to keep track of beginning element of the sub array.

>> Continue doing this until end of array. If currSum din’t match reqdSum at any point, then we can conclude that no subarray is found.