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.

 

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

avatar
  Subscribe  
newest oldest most voted
Notify of
Rahul Khandelwal
Guest
Rahul Khandelwal

Mar
Guest

This was my interview question but the interviewer insisted to solve it through recursion.
I found some code which solve it recursive but the output is Boolean and I’m training to update it to get sub arrays out of it.

Akshay
Guest
Akshay

Hi Guys,

Can somebody explain me about usage of hashMap ?