This program demonstrates how to find a subarray with a given sum using a hash map for efficient lookups.

Program Structure

1. Imports: The program imports necessary packages.
2. Function findSubarrayWithSum: This function takes an integer slice and a target sum. It uses a hash map to keep track of cumulative sums and their indices.
3. Logic: As we iterate through the array, we maintain a cumulative sum and check if the current cumulative sum minus the target sum exists in the hash map. If it does, we have found a subarray.
4. Main Function: This part of the code initializes the array and the target sum, then calls the function to find the subarray.

Go Program

package main

import (
    "fmt"
)

// findSubarrayWithSum finds the subarray with the given sum
func findSubarrayWithSum(arr []int, targetSum int) (int, int) {
    // Create a map to store the cumulative sum and its corresponding index
    sumMap := make(map[int]int)
    cumulativeSum := 0

    // Iterate over the array
    for i, value := range arr {
        cumulativeSum += value

        // Check if the cumulative sum is equal to the target sum
        if cumulativeSum == targetSum {
            return 0, i // Subarray found from index 0 to i
        }

        // Check if there exists a cumulative sum that would give the target sum
        if index, exists := sumMap[cumulativeSum-targetSum]; exists {
            return index + 1, i // Subarray found from index index+1 to i
        }

        // Store the cumulative sum with its index
        sumMap[cumulativeSum] = i
    }

    return -1, -1 // Return -1, -1 if no subarray is found
}

func main() {
    arr := []int{1, 2, 3, 7, 5}
    targetSum := 12

    startIndex, endIndex := findSubarrayWithSum(arr, targetSum)

    if startIndex != -1 {
        fmt.Printf("Subarray found from index %d to %d\n", startIndex, endIndex)
    } else {
        fmt.Println("No subarray with the given sum found.")
    }
}

Explanation of the Code

– The function findSubarrayWithSum takes two parameters:

• arr: A slice of integers representing the array.
• targetSum: An integer representing the target sum we want to find.

– The cumulative sum is tracked as we iterate through the array, and a map is used to record previously encountered sums for quick lookup.

– If a subarray is found that sums to the target, the starting and ending indices are returned. If no subarray is found, -1, -1 is returned.

Usage

To run this program, ensure you have Go installed on your system. Save the code in a file with a .go extension, and execute it using the command:

go run filename.go