Question

How to find subarray from a given sum in C++

Answer 1

#include <bits/stdc++.h> 

using namespace std; 

void find_sub_array(int arr[], int len, int sum, int &start, int &end) { 
    unordered_map<int, int> map; 
    int current_sum = 0; 

    for (int i = 0; i < len; i++) { 
        current_sum = current_sum + arr[i]; 

        if (current_sum == sum) { 
            end = i;
            return; 
        } 

        if (map.find(current_sum - sum) != map.end()) { 
            start = map[current_sum - sum] + 1;
            end  = i;
            return; 
        } 
        map[current_sum] = i; 
    } 
} 
  
int main() 
{ 
    int arr[] = {6, 1, 4, -1, 5, -1, 2}; 
    int len = sizeof(arr)/sizeof(arr[0]); 
    int sum = 9, start = 0, end = 0;
  
    find_sub_array(arr, len, sum, start , end); 
    
    cout << "from index " << start << " to " << end << endl; 
  
    return 0; 
} 


/*
run:

from index 1 to 4

*/

 

70+ SQL courses for beginners and professionals