# 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.

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.

## Java

Output:

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

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 🙂

Subscribe
Notify of
Guest
Rahul Khandelwal

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.

Guest
Akshay

Hi Guys,

Can somebody explain me about usage of hashMap ?