Encuentra subarreglo con suma dada | Juego 2 (maneja números negativos)

Dada una array desordenada de enteros, encuentre una subarreglo que se sume a un número dado. Si hay más de un subarreglo con la suma del número dado, imprima cualquiera de ellos.

Ejemplos:  

Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Output: Sum found between indexes 2 and 4
Explanation: Sum of elements between indices
2 and 4 is 20 + 3 + 10 = 33

Input: arr[] = {10, 2, -2, -20, 10}, sum = -10
Output: Sum found between indexes 0 to 3
Explanation: Sum of elements between indices
0 and 3 is 10 + 2 - 2 - 20 = -10

Input: arr[] = {-10, 0, 2, -2, -20, 10}, sum = 20
Output: No subarray with given sum exists
Explanation: There is no subarray with the given sum

Nota: Hemos discutido una solución que no maneja enteros negativos aquí . En este post también se manejan enteros negativos.

Enfoque simple: una solución simple es considerar todos los subarreglos uno por uno y verificar la suma de cada subarreglo. El siguiente programa implementa la solución simple. Ejecute dos bucles: el bucle exterior elige un punto de inicio I y el bucle interior prueba todos los subarreglos a partir de i.

Algoritmo:  

1. Atraviesa la array de principio a fin.
2. Desde cada índice, comience otro bucle desde i hasta el final de la array para obtener todos los subarreglos a partir de i, y mantenga una suma variable para calcular la suma. Para cada índice en el bucle interno, actualice sum = sum + array[j]Si la suma es igual a la suma dada, imprima el subarreglo.
3. Para cada índice en la actualización del bucle interno sum = sum + array[j]
4. Si la suma es igual a la suma dada, imprima el subarreglo.

/* A simple program to print subarray
with sum as given sum */
#include <bits/stdc++.h>
using namespace std;
  
/* Returns true if the there is a subarray
of arr[] with sum equal to 'sum' otherwise
returns false. Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
    int curr_sum, i, j;
  
    // Pick a starting point
    for (i = 0; i < n; i++) {
        curr_sum = 0;
  
        // try all subarrays starting with 'i'
        for (j = i ; j < n; j++) {
           curr_sum = curr_sum + arr[j];
           
            if (curr_sum == sum) {
                cout << "Sum found between indexes "
                     << i << " and " << j ;
                return 1;
            }
             
            
        }
    }
  
    cout << "No subarray found";
    return 0;
}
  
// Driver Code
int main()
{
    int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int sum = 23;
    subArraySum(arr, n, sum);
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG
{
   
/* Returns true if the there is a subarray
of arr[] with sum equal to 'sum' otherwise
returns false. Also, prints the result */
static int subArraySum(int arr[], int n, int sum)
{
    int curr_sum, i, j;
  
    // Pick a starting point
    for (i = 0; i < n; i++) {
        curr_sum = 0;
  
        // try all subarrays starting with 'i'
        for (j = i ; j < n; j++) {
           curr_sum = curr_sum + arr[j];
           
            if (curr_sum == sum) {
                System.out.print( "Sum found between indexes "
                     + i + " and " + j);
                return 1;
            }
             
            
        }
    }
  
    System.out.print("No subarray found");
    return 0;
}
 
// Driver Code
public static void main (String[] args)
{
    int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
    int n = arr.length;
    int sum = 23;
    subArraySum(arr, n, sum);
}
}
 
// This code is contributed by code_hunt.

# Python3 program to print subarray
# with sum as given sum
 
 
# Returns true if the there is a subarray
# of arr[] with sum equal to 'sum' otherwise
# returns false. Also, prints the result */
def subArraySum(arr, n, sum):
 
    # Pick a starting point
    for i in range(n):
        curr_sum = 0
        # try all subarrays starting with 'i'
        for j in range(i, n):
            curr_sum += arr[j]
            if (curr_sum == sum):
                print("Sum found between indexes", i, "and", j)
                return
 
    print("No subarray found")
 
 
# Driver Code
arr = [15, 2, 4, 8, 9, 5, 10, 23]
n = len(arr)
sum = 23
 
# Function Call
subArraySum(arr, n, sum)
 
 
# This code is contributed by phasing17

/* A simple program to print subarray
with sum as given sum */
 
using System;
 
public static class GFG {
    /* Returns true if the there is a subarray
    of arr[] with sum equal to 'sum' otherwise
    returns false. Also, prints the result */
 
    public static int subArraySum(int[] arr, int n, int sum)
    {
        int curr_sum;
        int i;
        int j;
 
        // Pick a starting point
        for (i = 0; i < n; i++) {
            curr_sum = 0;
 
            // try all subarrays starting with 'i'
            for (j = i; j < n; j++) {
                curr_sum = curr_sum + arr[j];
 
                if (curr_sum == sum) {
                    Console.Write(
                        "Sum found between indexes ");
                    Console.Write(i);
                    Console.Write(" and ");
                    Console.Write(j);
                    return 1;
                }
            }
        }
 
        Console.Write("No subarray found");
        return 0;
    }
 
    // Driver Code
    public static void Main()
    {
        int[] arr = { 15, 2, 4, 8, 9, 5, 10, 23 };
        int n = arr.Length;
        int sum = 23;
        subArraySum(arr, n, sum);
    }
}
 
// This code is contributed by Aarti_Rathi

/* JavaScript program to print subarray
with sum as given sum */
 
  
/* Returns true if the there is a subarray
of arr[] with sum equal to 'sum' otherwise
returns false. Also, prints the result */
function subArraySum(arr, n, sum)
{
    var curr_sum, i, j;
  
    // Pick a starting point
    for (i = 0; i < n; i++) {
        curr_sum = 0;
  
        // try all subarrays starting with 'i'
        for (j = i ; j < n; j++) {
           curr_sum = curr_sum + arr[j];
           
            if (curr_sum == sum) {
                console.log("Sum found between indexes " + i + " and " + j);
                return;
            }
        }
    }
  
    console.log("No subarray found");
}
  
// Driver Code
var arr = [ 15, 2, 4, 8, 9, 5, 10, 23 ];
var n = arr.length;
var sum = 23;
 
//Function Call
subArraySum(arr, n, sum);
 
 
//This code is contributed by phasing17

Sum found between indexes 1 and 4

Enfoque: La idea es almacenar la suma de elementos de cada prefijo de la array en un mapa hash, es decir, cada índice almacena la suma de elementos hasta ese mapa hash de índice. Entonces, para verificar si hay un subarreglo con una suma igual a s , verifique cada índice i y sume ese índice como x . Si hay un prefijo con una suma igual a x – s , entonces se encuentra el subarreglo con la suma dada. 

Algoritmo:  

1. Cree un Hashmap ( hm ) para almacenar un par clave-valor, es decir, clave = prefijo suma y valor = su índice, y una variable para almacenar la suma actual ( suma = 0 ) y la suma del subarreglo como s
2. Atraviesa la array de principio a fin.
3. Para cada elemento, actualice la suma, es decir, sum = sum + array[i]
4. Si la suma es igual a s, imprima que el subarreglo con la suma dada es de 0 a i
5. Si hay alguna clave en el HashMap que es igual a sum – s , imprima que el subarreglo con la suma dada es de hm [sum – s] a i
6. Coloque la suma y el índice en el hashmap como un par clave-valor.

Ejecución en seco del enfoque anterior: 

Implementación:  

// C++ program to print subarray with sum as given sum
#include<bits/stdc++.h>
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<int, int> 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 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 cumulative sum till that point
        int cur_sum = 0;
        int start = 0;
        int end = -1;
        HashMap<Integer, Integer> 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 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

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 cumulative sum till that point
        int cur_sum = 0;
        int start = 0;
        int end = -1;
        Dictionary<int, int> hashMap = new Dictionary<int, int>();
 
        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

<script>
 
// Javascript program to print subarray with sum as given sum
 
    function subArraySum(arr, n, sum) {
        //cur_sum to keep track of cumulative sum till that point
        let cur_sum = 0;
        let start = 0;
        let end = -1;
        let hashMap = new Map();
   
        for (let 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.has(cur_sum - sum)) {
                start = hashMap.get(cur_sum - sum) + 1;
                end = i;
                break;
            }
            //if value is not present then add to hashmap
            hashMap.set(cur_sum, i);
   
        }
        // if end is -1 : means we have reached end without the sum
        if (end == -1) {
            document.write("No subarray with given sum exists");
        }
        else {
            document.write("Sum found between indexes "
                            + start + " to " + end);
        }
   
    }
 
// Driver program
 
         let arr = [10, 2, -2, -20, 10];
        let n = arr.length;
        let sum = -10;
        subArraySum(arr, n, sum);
       
</script>

Sum found between indexes 0 to 3

Análisis de Complejidad:  

• Complejidad temporal: O(N). 
  Si el hashing se realiza con la ayuda de una array, esta es la complejidad del tiempo. En caso de que los elementos no se puedan codificar en una array, también se puede usar un mapa hash como se muestra en el código anterior.
• Espacio auxiliar: O(n). 
  Como se necesita un HashMap, esto ocupa un espacio lineal.

Encuentre subarreglo con suma dada con negativos permitidos en espacio constante
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.