Program Overview

This Java program finds a contiguous subarray within a one-dimensional array of integers that sums to a specified value. It utilizes a hash map to store the cumulative sums and efficiently checks for the existence of the required sum.

Program Structure

• Function: findSubarrayWithSum
  • Parameters: int[] array, int targetSum
  • Returns: void (prints the indices of the subarray if found)
• Main Method
  • Tests the function with a sample array and target sum.

Java Code

import java.util.HashMap;

public class SubarraySum {
    
    /**
     * Finds a subarray with the given sum.
     * 
     * @param array The input array of integers.
     * @param targetSum The target sum to find in the subarray.
     */
    public static void findSubarrayWithSum(int[] array, int targetSum) {
        HashMap<Integer, Integer> sumMap = new HashMap<>();
        int cumulativeSum = 0;
        
        for (int i = 0; i < array.length; i++) {
            // Update cumulative sum
            cumulativeSum += array[i];
            
            // Check if cumulative sum equals the target sum
            if (cumulativeSum == targetSum) {
                System.out.println("Subarray found from index 0 to " + i);
                return;
            }
            
            // Check if there is a subarray (cumulativeSum - targetSum) in the map
            if (sumMap.containsKey(cumulativeSum - targetSum)) {
                System.out.println("Subarray found from index " + (sumMap.get(cumulativeSum - targetSum) + 1) + " to " + i);
                return;
            }
            
            // Store the cumulative sum with its index
            sumMap.put(cumulativeSum, i);
        }
        
        System.out.println("No subarray found with the given sum.");
    }

    public static void main(String[] args) {
        int[] array = {1, 2, 3, 7, 5};
        int targetSum = 12;
        findSubarrayWithSum(array, targetSum);
    }
}

Explanation of the Code

1. **Import Statements**: The program imports the HashMap class from the Java Collections Framework to facilitate storing cumulative sums.

2. **findSubarrayWithSum Method**: This method implements the core logic to find the subarray.

• A cumulative sum variable keeps track of the sum of elements as we iterate through the array.
• A HashMap is used to store previously seen cumulative sums along with their corresponding indices.
• For each element, we check if the cumulative sum equals the target sum. If it does, we print the starting and ending indices.
• We also check if the difference between the cumulative sum and the target sum exists in the map, indicating a valid subarray.

3. **Main Method**: It initializes an example array and a target sum, and calls the findSubarrayWithSum method.

Conclusion

This program efficiently finds a contiguous subarray with a specified sum using a hash map, allowing it to operate in linear time, O(n), where n is the number of elements in the input array.