Make delicious recipes!

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[0];
start=0;
end=0;
while (end < arr.length)
{
    if (currSum == givenSum)
    {
        print ("Found given sum from " + start + " to " + end);
    }
    
    if (currSum <= givenSum)
    {
        end++;
        if (end < arr.length)
            currSum = currSum + arr[end];
    }
    else
    {
        currSum = currSum - arr[start];
        start++;
    }
}






Like us on Facebook to remain in touch
with the latest in technology and tutorials!


Got a thought to share or found a
bug in the code?
We'd love to hear from you:

Name:
Email: (Your email is not shared with anybody)
Comment:

Facebook comments:

Site Owner: Sachin Goyal