Program Overview

This program aims to find a continuous subarray within a one-dimensional array of numbers that sums up to a given target value. The program utilizes a hash table (unordered_map in C++) for efficient lookups, making the search process faster.

Program Structure

1. Input: The program takes an array of integers and a target sum.
2. Logic: It maintains a running sum and uses a hash table to track the sums encountered so far.
3. Output: If a subarray with the given sum is found, the program prints its start and end indices; otherwise, it indicates that no such subarray exists.

C++ Code Implementation

#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

/**
 * Function to find a subarray with a given sum using hashing.
 * 
 * @param arr The input array of integers.
 * @param n The size of the array.
 * @param target_sum The target sum to find in the subarray.
 */
void findSubarrayWithSum(const vector<int> &arr, int n, int target_sum) {
    unordered_map<int, int> sum_map; // Hash table to store sum and its index
    int current_sum = 0; // Variable to store the current sum

    for (int i = 0; i < n; i++) {
        current_sum += arr[i]; // Update the current sum

        // Check if the current sum equals the target sum
        if (current_sum == target_sum) {
            cout << "Subarray found from index 0 to " << i << endl;
            return;
        }

        // Check if there is a subarray (current_sum - target_sum) in the hash map
        if (sum_map.find(current_sum - target_sum) != sum_map.end()) {
            cout << "Subarray found from index " << sum_map[current_sum - target_sum] + 1 << " to " << i << endl;
            return;
        }

        // Store the current sum with its index
        sum_map[current_sum] = i;
    }

    cout << "No subarray with the given sum exists." << endl;
}

int main() {
    vector<int> arr = {1, 2, 3, 7, 5};
    int target_sum = 12;
    int n = arr.size();

    findSubarrayWithSum(arr, n, target_sum);

    return 0;
}

Explanation of the Code

• The program includes necessary headers for input-output operations and using the hash table.
• The function findSubarrayWithSum accepts the array, its size, and the target sum.
• A hash table, sum_map, is used to store cumulative sums and their corresponding indices.
• The main loop iterates through the array, updating the current cumulative sum.
• It checks if the current cumulative sum equals the target sum. If so, it prints the indices of the subarray.
• If not, it checks if the difference (current sum – target sum) exists in the hash table, indicating a valid subarray.
• If neither condition is met, it stores the current cumulative sum and its index in the hash table.
• Finally, if no valid subarray is found, it outputs a message indicating that.

How to Run the Program

1. Copy the code into a C++ compiler or IDE.
2. Compile the program and run it.
3. The output will indicate the indices of the subarray that matches the target sum, if it exists.

Conclusion

This C++ program efficiently finds a subarray with a specified sum using hashing. The use of a hash table allows for an average time complexity of O(n), making it suitable for large datasets.