Subarray with Given Sum in C++

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

C++ Program

#include <iostream>
#include <vector>
using namespace std;

/**
 * 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 A vector containing the starting and ending indices of the subarray, or {-1, -1} if no such subarray exists.
 */
vector<int> findSubarrayWithSum(const vector<int>& arr, int targetSum) {
    int start = 0, end = 0, currentSum = 0;

    // Iterate over the array
    while (end < arr.size()) { // 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 {start, end};
        }

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

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

/**
 * Main method to test the findSubarrayWithSum method.
 *
 * @param argc Command line arguments count.
 * @param argv Command line arguments vector.
 * @return int Return code.
 */
int main() {
    vector<int> arr = {1, 2, 3, 7, 5};
    int targetSum = 12;
    vector<int> result = findSubarrayWithSum(arr, targetSum);

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

    return 0;
}
    

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