Find subarray with given sum | Set 2 (Handles Negative Numbers)

Given an unsorted array of integers, find a subarray which adds to a given number. If there are more than one subarrays with the sum as the given number, print any of them.

Examples:

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4

Input: arr[] = {10, 2, -2, -20, 10}, sum = -10
Ouptut: Sum found between indexes 0 to 3

Input: arr[] = {-10, 0, 2, -2, -20, 10}, sum = 20
Ouptut: No subarray with given sum exists

We have discussed a solution that do not handles negative integers here. In this post, negative integers are also handled.

A simple solution is to consider all subarrays one by one and check if sum of every subarray is equal to given sum or not. The complexity of this solution would be O(n^2).

An efficient way is to use a map. The idea is to maintain sum of elements encountered so far in a variable (say curr_sum). Let the given number is sum. Now for each element, we check if curr_sum – sum exists in the map or not. If we found it in the map that means, we have a subarray present with given sum, else we insert curr_sum into the map and proceed to next element. If all elements of the array are processed and we didn’t find any subarray with given sum, then subarray doesn’t exists.

Below is the implementation of above idea –

C++

 // C++ program to print subarray with sum as given sum #include using namespace std;    // Function to print subarray with sum as given sum void subArraySum(int arr[], int n, int sum) {     // create an empty map     unordered_map map;        // Maintains sum of elements so far     int curr_sum = 0;        for (int i = 0; i < n; i++)     {         // add current element to curr_sum         curr_sum = curr_sum + arr[i];            // if curr_sum is equal to target sum         // we found a subarray starting from index 0         // and ending at index i         if (curr_sum == sum)         {             cout << "Sum found between indexes "                  << 0 << " to " << i << endl;             return;         }            // If curr_sum - sum already exists in map         // we have found a subarray with target sum         if (map.find(curr_sum - sum) != map.end())         {             cout << "Sum found between indexes "                  << map[curr_sum - sum] + 1                  << " to " << i << endl;             return;         }            map[curr_sum] = i;     }        // If we reach here, then no subarray exists     cout << "No subarray with given sum exists"; }    // Driver program to test above function int main() {     int arr[] = {10, 2, -2, -20, 10};     int n = sizeof(arr)/sizeof(arr[0]);     int sum = -10;        subArraySum(arr, n, sum);        return 0; }

Java

 // Java program to print subarray with sum as given sum import java.util.*;    class GFG {        public static void subArraySum(int[] arr, int n, int sum) {         //cur_sum to keep track of cummulative sum till that point         int cur_sum = 0;         int start = 0;         int end = -1;         HashMap hashMap = new HashMap<>();            for (int i = 0; i < n; i++) {             cur_sum = cur_sum + arr[i];             //check whether cur_sum - sum = 0, if 0 it means             //the sub array is starting from index 0- so stop             if (cur_sum - sum == 0) {                 start = 0;                 end = i;                 break;             }             //if hashMap already has the value, means we already              // have subarray with the sum - so stop             if (hashMap.containsKey(cur_sum - sum)) {                 start = hashMap.get(cur_sum - sum) + 1;                 end = i;                 break;             }             //if value is not present then add to hashmap             hashMap.put(cur_sum, i);            }         // if end is -1 : means we have reached end without the sum         if (end == -1) {             System.out.println("No subarray with given sum exists");         } else {             System.out.println("Sum found between indexes "                              + start + " to " + end);         }        }        // Driver code     public static void main(String[] args) {         int[] arr = {10, 2, -2, -20, 10};         int n = arr.length;         int sum = -10;         subArraySum(arr, n, sum);        } }

Python3

 # Python3 program to print subarray with sum as given sum     # Function to print subarray with sum as given sum  def subArraySum(arr, n, Sum):          # create an empty map      Map = {}           # Maintains sum of elements so far      curr_sum = 0           for i in range(0,n):                  # add current element to curr_sum          curr_sum = curr_sum + arr[i]               # if curr_sum is equal to target sum          # we found a subarray starting from index 0          # and ending at index i          if curr_sum == Sum:                          print("Sum found between indexes 0 to", i)             return                           # If curr_sum - sum already exists in map          # we have found a subarray with target sum          if (curr_sum - Sum) in Map:                          print("Sum found between indexes",                    Map[curr_sum - Sum] + 1, "to", i)                             return               Map[curr_sum] = i           # If we reach here, then no subarray exists      print("No subarray with given sum exists")           # Driver program to test above function  if __name__ == "__main__":          arr = [10, 2, -2, -20, 10]      n = len(arr)      Sum = -10           subArraySum(arr, n, Sum)       # This code is contributed by Rituraj Jain

C#

 using System; using System.Collections.Generic;    // C# program to print subarray with sum as given sum     public class GFG {        public static void subArraySum(int[] arr, int n, int sum)     {         //cur_sum to keep track of cummulative sum till that point          int cur_sum = 0;         int start = 0;         int end = -1;         Dictionary hashMap = new Dictionary();            for (int i = 0; i < n; i++)         {             cur_sum = cur_sum + arr[i];             //check whether cur_sum - sum = 0, if 0 it means              //the sub array is starting from index 0- so stop              if (cur_sum - sum == 0)             {                 start = 0;                 end = i;                 break;             }             //if hashMap already has the value, means we already               // have subarray with the sum - so stop              if (hashMap.ContainsKey(cur_sum - sum))             {                 start = hashMap[cur_sum - sum] + 1;                 end = i;                 break;             }             //if value is not present then add to hashmap              hashMap[cur_sum] = i;            }         // if end is -1 : means we have reached end without the sum          if (end == -1)         {             Console.WriteLine("No subarray with given sum exists");         }         else         {             Console.WriteLine("Sum found between indexes " + start + " to " + end);         }        }        // Driver code      public static void Main(string[] args)     {         int[] arr = new int[] {10, 2, -2, -20, 10};         int n = arr.Length;         int sum = -10;         subArraySum(arr, n, sum);        } }    // This code is contributed by Shrikant13

Output:

Sum found between indexes 0 to 3

Time complexity of above solution is O(n) as we are doing only one traversal of the array.

Auxiliary space
used by the program is O(n).