Subarray with Given Sum in Java

This document explains how to find a subarray with a given sum in an array using Java. The solution provided is based on the sliding window approach.

Problem Statement

Given an array of integers and a target sum, find a continuous subarray that adds up to the target sum. If such a subarray exists, return the starting and ending indices of the subarray. If no such subarray exists, return -1 for both indices.

Approach

The approach used here is the sliding window technique. The idea is to use two pointers (start and end) to maintain a window that contains the current subarray being checked. If the sum of the current window is less than the target sum, expand the window by moving the end pointer to the right. If the sum is greater than the target, shrink the window by moving the start pointer to the right. This way, we efficiently find the subarray with the given sum.

Java Program

public class SubarrayWithGivenSum {
    /**
     * Finds the subarray with a given sum.
     *
     * @param arr The input array of integers.
     * @param targetSum The target sum to find in the subarray.
     * @return An array containing the starting and ending indices of the subarray, or [-1, -1] if no such subarray exists.
     */
    public static int[] findSubarrayWithSum(int[] arr, int targetSum) {
        int start = 0, end = 0, currentSum = 0;

        // Iterate over the array
        while (end < arr.length) { // Add the current element to the current sum currentSum += arr[end]; // Shrink the window from the left if the current sum exceeds the target sum while (currentSum > targetSum && start <= end) {
                currentSum -= arr[start];
                start++;
            }

            // Check if the current sum is equal to the target sum
            if (currentSum == targetSum) {
                return new int[]{start, end};
            }

            // Move to the next element
            end++;
        }

        // Return [-1, -1] if no subarray with the given sum is found
        return new int[]{-1, -1};
    }

    /**
     * Main method to test the findSubarrayWithSum method.
     *
     * @param args Command line arguments.
     */
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 7, 5};
        int targetSum = 12;
        int[] result = findSubarrayWithSum(arr, targetSum);

        if (result[0] != -1) {
            System.out.println("Subarray with given sum found from index " + result[0] + " to " + result[1]);
        } else {
            System.out.println("No subarray with the given sum found.");
        }
    }
}
    

Explanation

The program consists of two main parts: the findSubarrayWithSum method and the main method.

findSubarrayWithSum Method

This method takes two parameters: an array of integers and the target sum. It uses the sliding window approach to find the subarray that sums to the target. It maintains a window defined by two pointers, start and end. It expands the window by moving the end pointer and shrinks it by moving the start pointer as needed. If it finds a window whose sum equals the target, it returns the starting and ending indices of this window. If no such subarray is found, it returns [-1, -1].

main Method

This method is used to test the findSubarrayWithSum method. It creates an array and a target sum, calls the method with these values, and prints the result.

How to Run the Program

1. Copy the Java code into a file named SubarrayWithGivenSum.java.
2. Open a terminal or command prompt and navigate to the directory containing the file.
3. Compile the program using the command: javac SubarrayWithGivenSum.java
4. Run the program using the command: java SubarrayWithGivenSum

If the subarray with the given sum is found, the program will print the starting and ending indices. Otherwise, it will indicate that no such subarray exists.