Find all subarrays with a given sum
Problem: Given an unsorted array of non-negative integers, find all the subarrays whose sum is a given number K
Hint: This can be done in O(n) even though the number of subarrays is n2
Solution: Keep on adding elements in current_sum till its less than the given sum.
If it becomes greater than given sum, start subtracting elements from the start of the array till its greater than given sum.
currSum = arr;
while (end < arr.length)
if (currSum == givenSum)
print ("Found given sum from " + start + " to " + end);
if (currSum <= givenSum)
if (end < arr.length)
currSum = currSum + arr[end];
currSum = currSum - arr[start];