Find subarrays with given sum in an array

Given an array of integers, find subarrays with given sum in it.

 

For example,


Input:

A[] = { 3, 4, -7, 1, 3, 3, 1, -4 }
Sum = 7

Output:

Subarrays with given sum are

{ 3, 4 }
{ 3, 4, -7, 1, 3, 3 }
{ 1, 3, 3 }
{ 3, 3, 1 }

 

1. Naive solution

 

Simple solution would be to consider all subarrays and calculate sum of their elements. If the sum of the subarray is equal to the given sum, we print it.

 

C++

Download   Run Code

Output:

[0..1] — { 3 4 }
[0..5] — { 3 4 -7 1 3 3 }
[3..5] — { 1 3 3 }
[4..6] — { 3 3 1 }

 
This approach takes O(n3) time as subarray sum is calculated in O(1) time for each of n2 subarrays and it takes O(n) time to print a sub-array.

 


 

2. Hashing

 

We can also use hashing to find subarrays with given sum in an array by using a map of vector or a multi-map for storing end index of all subarrays having given sum. The idea is to traverse the given array, and maintain sum of elements seen so far. At any index i, let k be the difference between sum of elements seen so far and given sum. Now if key k is present in the map, there exists at-least one subarray with the given sum ending at current index i and we print all such subarrays.

C++

Download   Run Code

Java

Download   Run Code



Output:

[0..1] — { 3 4 }
[0..5] — { 3 4 -7 1 3 3 }
[3..5] — { 1 3 3 }
[4..6] — { 3 3 1 }

 

 
Thanks for reading.

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz