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.