Question

Find subarray with given sum in java.

int arr[] = {1,4,20,3,10,5}, sum = 33;

int arr[] = {10, 2, -2, -20, 10}, sum = -10;

Answer 1

Here the given an unsorted array of integers and find a sub-array which adds to a given number.

To see this question comes one solution in our mind like: Brute force solution.

The Brute force solution the Time Complexity O(n^2). See the following running java code to find a sub-array with given sum:-

public class FindSubarrayWithGivenSum {

public static void main(String[] args) {

int arr[] = {10, 2, -2, -20, 10}, sum = -10;

getSubArrayIndex(arr, sum);

}

//Brute force solution

//1+2+3+4........+n = n*(n+1)/2 = O(n^2)

//Time Complexity O(n^2)

private static void getSubArrayIndex(int[] arr, int sum) {

for(int i=0; i<arr.length; i++) {

int temp_sum = 0;

for(int j=i; j<arr.length; j++) {

temp_sum+=arr[j];

if(temp_sum==sum) {

System.out.println("Sum found between "+ i + " and " + j);

System.exit(0);

}

}

}

System.out.println("Could not found sub-array");

}

}

Output:- Sum found between 0 and 3

Answer 2

Now, i am going to give you, a solution to find sub-array with given sum.

To find sub-array with given sum in just O(n) time Complexity but this solution will take O(n) Space(Auxiliary) Complexity. As per my thinking, this solution is more efficient because  now a days space does't matter. More important to save time complexity.

The bellow solution will also handle the negative integer.

See the running code to find a sub-array with given sum:-

public class FindSubarrayWithGivenSum {

public static void main(String[] args) {

// int arr[] = {1,4,20,3,10,5};

// int sum = 33;

int arr[] = {10, 2, -2, -20, 10}, sum = -10;

getSubArrayIndex(arr, sum);

}

//It handles Negative Numbers

//Time Complexity O(n)

//Space(Auxiliary) Complexity O(n)

private static void getSubArrayIndex(int[] arr, int sum) {

Map<Integer, Integer> map = new HashMap<>();

int prefix_sum = 0;

for(int i=0; i<arr.length; i++) {

prefix_sum+= arr[i];

//Check whether prefix_sum - sum = 0, if 0 it means the sub array is starting from index 0- so stop 

if(prefix_sum == sum) {

System.out.println("0 to " + i);

break;

}

//if hashMap has the value, means we have sub-array with the sum - so now stop 

if(map.containsKey(prefix_sum-sum)) {

int startIndex = map.get(prefix_sum-sum)+1;

System.out.println("Sum found between "+ startIndex + " and " + i);

break;

}

map.put(prefix_sum, i);

}

}

}

Output:-0 to 3