Subarray with Given Sum in Go

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

Go Program

package main

import (
    "fmt"
)

// findSubarrayWithSum finds the subarray with a given sum.
func findSubarrayWithSum(arr []int, targetSum int) (int, int) {
    start, end, currentSum := 0, 0, 0

    // Iterate over the array
    for end < len(arr) { // 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 for currentSum > targetSum && start <= end {
            currentSum -= arr[start]
            start++
        }

        // Check if the current sum is equal to the target sum
        if currentSum == targetSum {
            return start, end
        }

        // Move to the next element
        end++
    }

    // Return -1, -1 if no subarray with the given sum is found
    return -1, -1
}

// main function to test the findSubarrayWithSum function.
func main() {
    arr := []int{1, 2, 3, 7, 5}
    targetSum := 12
    start, end := findSubarrayWithSum(arr, targetSum)

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

Explanation

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

findSubarrayWithSum 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 Function

This function is used to test the findSubarrayWithSum 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 Go code into a file named main.go.
2. Open a terminal or command prompt and navigate to the directory containing the file.
3. Run the program using the command: go run main.go

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.