This program demonstrates how to find a contiguous subarray within a one-dimensional array of numbers that sums to a specified target value. We use a hashing technique for efficient lookup.

Program Code

def find_subarray_with_sum(arr, target_sum):
    """
    Find a contiguous subarray in 'arr' that sums to 'target_sum'.

    Parameters:
    arr (list): The input list of integers.
    target_sum (int): The target sum to find.

    Returns:
    tuple: Start and end indices of the subarray if found, otherwise (-1, -1).
    """
    # Create a dictionary to store the cumulative sum and its index
    sum_map = {}
    cumulative_sum = 0

    for index, value in enumerate(arr):
        cumulative_sum += value
        
        # Check if the cumulative sum is equal to the target sum
        if cumulative_sum == target_sum:
            return (0, index)  # Found a subarray from index 0 to current index
        
        # Check if there is a subarray with the required sum
        if (cumulative_sum - target_sum) in sum_map:
            return (sum_map[cumulative_sum - target_sum] + 1, index)  # Return the indices
        
        # Store the cumulative sum with its index
        sum_map[cumulative_sum] = index

    return (-1, -1)  # Return (-1, -1) if no subarray found

# Example Usage
arr = [10, 2, -2, -20, 10]
target_sum = -10
result = find_subarray_with_sum(arr, target_sum)

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

Program Structure

The program consists of a single function find_subarray_with_sum that takes two arguments: an array of integers and a target sum. Here’s how it works:

1. Cumulative Sum Calculation: As we iterate through the array, we maintain a cumulative sum of the elements.
2. Hash Map for Lookup: We use a dictionary to store the cumulative sums we encounter along with their corresponding indices.
3. Check for Subarray: For each element, we check if the cumulative sum minus the target sum exists in the dictionary. If it does, we have found a subarray that sums to the target.
4. Return Indices: If a matching sum is found, we return the start and end indices. If no subarray is found after checking all elements, we return (-1, -1).

Complexity Analysis

• Time Complexity: O(n), where n is the number of elements in the array. We traverse the array once.
• Space Complexity: O(n), in the worst case, where all cumulative sums are stored in the hash map.

Example Usage

In the example usage provided, the function is called with an array and a target sum. If a subarray is found, it prints the indices of the subarray; otherwise, it indicates that no subarray was found.