Subarray with Given Sum in Python

This document explains how to find a subarray with a given sum in an array using Python. 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.

Python Program

def find_subarray_with_sum(arr, target_sum):
    """
    Finds the subarray with a given sum.

    :param arr: List[int], The input array of integers.
    :param target_sum: int, The target sum to find in the subarray.
    :return: List[int], An array containing the starting and ending indices of the subarray, or [-1, -1] if no such subarray exists.
    """
    start = 0
    current_sum = 0

    # Iterate over the array
    for end in range(len(arr)):
        # Add the current element to the current sum
        current_sum += arr[end]

        # Shrink the window from the left if the current sum exceeds the target sum
        while current_sum > target_sum and start <= end:
            current_sum -= arr[start]
            start += 1

        # Check if the current sum is equal to the target sum
        if current_sum == target_sum:
            return [start, end]

    # Return [-1, -1] if no subarray with the given sum is found
    return [-1, -1]

# Main method to test the find_subarray_with_sum function
if __name__ == "__main__":
    arr = [1, 2, 3, 7, 5]
    target_sum = 12
    result = find_subarray_with_sum(arr, target_sum)

    if result[0] != -1:
        print(f"Subarray with given sum found from index {result[0]} to {result[1]}")
    else:
        print("No subarray with the given sum found.")
    

Explanation

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

find_subarray_with_sum Function

This function 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 find_subarray_with_sum function. It creates an array and a target sum, calls the function with these values, and prints the result.

How to Run the Program

1. Copy the Python code into a file named subarray_with_given_sum.py.
2. Open a terminal or command prompt and navigate to the directory containing the file.
3. Run the program using the command: python subarray_with_given_sum.py

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.