# 1. Introduction

Given an unsorted array of integers, the task is to find all subarrays with a specified sum. This problem has various applications and is frequently asked in interviews. Let’s dive deep into solving this problem efficiently using a sliding window and hash map approach.

# 2. Program Steps

1. Initialize a *currentSum* to track the running sum of elements.

2. Use a hash map (*prefixSum*) to keep track of sum frequencies encountered so far.

3. Traverse through the array, and for each element, update the *currentSum*.

4. Check for the existence of *(currentSum – targetSum)* in the *prefixSum* map to identify the subarrays.

5. Update the *prefixSum* map with the *currentSum*.

# 3. Code Program

```
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class SubarrayGivenSum {
public static List<List<Integer>> findSubarrays(int[] arr, int targetSum) {
// List to store the result
List<List<Integer>> result = new ArrayList<>();
// Map to store prefix sum and its frequency
Map<Integer, Integer> prefixSum = new HashMap<>();
int currentSum = 0;
for (int i = 0; i < arr.length; i++) {
currentSum += arr[i];
if (currentSum == targetSum) {
result.add(new ArrayList<>(List.of(0, i)));
}
if (prefixSum.containsKey(currentSum - targetSum)) {
for (int count = 0; count < prefixSum.get(currentSum - targetSum); count++) {
result.add(new ArrayList<>(List.of(count + 1, i)));
}
}
prefixSum.put(currentSum, prefixSum.getOrDefault(currentSum, 0) + 1);
}
return result;
}
public static void main(String[] args) {
int[] arr = {10, 2, -2, -20, 10};
int targetSum = -10;
List<List<Integer>> subarrays = findSubarrays(arr, targetSum);
for (List<Integer> subarray : subarrays) {
System.out.println("Subarray from index " + subarray.get(0) + " to " + subarray.get(1));
}
}
}
```

### Output:

Subarray from index 1 to 3 Subarray from index 2 to 4

# 4. Step By Step Explanation

1. We start by initializing a *currentSum* to keep track of the sum of elements while iterating through the array.

2. A hash map, *prefixSum*, stores the frequency of each *currentSum* encountered.

3. While iterating through the array, for each element, we update *currentSum*.

4. If *currentSum* becomes equal to *targetSum*, it indicates that a subarray starting from the 0th index to the current index has the given sum.

5. If *(currentSum – targetSum)* exists in *prefixSum*, it means there are one or more subarrays ending at the current index which have the sum *targetSum*.

6. We then update the count of the current *currentSum* in the *prefixSum* map.

7. The result is a list of lists, where each inner list represents the start and end index of a subarray with sum *targetSum*.

8. The *main* function demonstrates the solution with a sample input.