Be the first user to complete this post

Add to List 
Find subarray with a sum to given number2  Handle negative numbers
Problem: Given an array (positive and negative) and an integer, find the subarray with sum is equal to the given integer.
Note: This problem is an extension of  find the subarray with sum to a Given Value, in which arrays with negative numbers are not handled.
Example:
Given input: [25, 12, 14, 22, 19, 15, 10, 23] K = 11. Subarray with sum = 11 Output: [14 22 19 ] Given input: [10, 0, 1, 20, 25, 30] K = 45 Subarray with sum = 45 Output: [20 25]
Approach:
Given : input[] and K
Idea: We need to find subarray input[a, b]  sum of elements from index a to b = K.
input[a, b] = input[0, b]  input[0, a1]
Steps:
 Initialize a map which will store the sum up to element at the current index and current index as a value.
 Initialize i = 0, j = 1.
 Initialize curr_sum = 0, keep adding elements during iteration.
 Iterate through array and for currenct index n,
 curr_sum = curr_sum + input[n].
 Check if curr_sum = K, we have found a subarray and means all the elements till the current element are included, do j = n, and break the loop.
 Check if the map contains curr_sum  K, if yes then we have found a subarray, get the index from the map for key curr_sum  K and do i = index + 1 and j = n, the elements from index i to j will have sum = K.
 Check if j!=1, means we have found the subarray during iteration. Print the elements from index i to index j. (input[i, j]), else if j==1 then no subarray exists with sum = K.
Time Complexity: O(N), Space Complexity: O(N)
Complete Code:
Output:
Given input: [25, 12, 14, 22, 19, 15, 10, 23] Subarray with sum = 55 14 22 19  Given input: [25, 12, 14, 22, 19, 15, 10, 23] Subarray with sum = 11 14 22 19  Given input: [10, 0, 1, 20, 25, 30] Subarray with sum = 45 20 25
Also Read: