Encuentra subarreglo con suma dada | Conjunto 1 (Números no negativos)

Posted on by Rudeus Greyrat

Dada una array no ordenada de enteros no negativos y una suma de enteros , encuentre una subarreglo continuo que se suma a una suma dada. Puede haber más de un subarreglo con suma como la suma dada, imprima primero ese subarreglo. 
Ejemplos: 

Entrada : arr[] = {1, 4, 20, 3, 10, 5}, suma = 33
Salida : Suma encontrada entre los índices 2 y 4
La suma de los elementos entre los índices 2 y 4 es 20 + 3 + 10 = 33

Entrada : arr[] = {1, 4, 0, 0, 3, 10, 5}, suma = 7
Salida : Suma encontrada entre los índices 1 y 4
La suma de los elementos entre los índices 1 y 4 es 4 + 0 + 0 + 3 = 7

Entrada : arr[] = {1, 4}, suma = 0
Salida : No se encontró subarreglo
No hay subarreglo con 0 suma

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, mantenga una suma variable para calcular la suma.
  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.

C++

/* 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 = arr[i];
  
        // try all subarrays starting with 'i'
        for (j = i + 1; j <= n; j++) {
            if (curr_sum == sum) {
                cout << "Sum found between indexes "
                     << i << " and " << j - 1;
                return 1;
            }
            if (curr_sum > sum || j == n)
                break;
            curr_sum = curr_sum + arr[j];
        }
    }
  
    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;
}
  
// This code is contributed
// by rathbhupendra

C

/* A simple program to print 
subarray with sum as given sum */
#include <stdio.h>
  
/* Returns true if the there is a subarray 
of arr[] with a 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 = arr[i];
  
        // try all subarrays starting with 'i'
        for (j = i + 1; j <= n; j++) {
            if (curr_sum == sum) {
                printf(
                    "Sum found between indexes %d and %d",
                    i, j - 1);
                return 1;
            }
            if (curr_sum > sum || j == n)
                break;
            curr_sum = curr_sum + arr[j];
        }
    }
  
    printf("No subarray found");
    return 0;
}
  
// Driver program to test above function
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

class SubarraySum {
    /* Returns true if the there is a 
subarray of arr[] with a 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 = arr[i];
  
            // try all subarrays starting with 'i'
            for (j = i + 1; j <= n; j++) {
                if (curr_sum == sum) {
                    int p = j - 1;
                    System.out.println(
                        "Sum found between indexes " + i
                        + " and " + p);
                    return 1;
                }
                if (curr_sum > sum || j == n)
                    break;
                curr_sum = curr_sum + arr[j];
            }
        }
  
        System.out.println("No subarray found");
        return 0;
    }
  
    public static void main(String[] args)
    {
        SubarraySum arraysum = new SubarraySum();
        int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
        int n = arr.length;
        int sum = 23;
        arraysum.subArraySum(arr, n, sum);
    }
}
  
// This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

# 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 = arr[i]
      
        # try all subarrays
        # starting with 'i'
        j = i + 1
        while j <= n:
          
            if curr_sum == sum_:
                print ("Sum found between")
                print("indexes % d and % d"%( i, j-1))
                  
                return 1
                  
            if curr_sum > sum_ or j == n:
                break
              
            curr_sum = curr_sum + arr[j]
            j += 1
  
    print ("No subarray found")
    return 0
  
# Driver program 
arr = [15, 2, 4, 8, 9, 5, 10, 23]
n = len(arr)
sum_ = 23
  
subArraySum(arr, n, sum_)
  
# This code is Contributed by shreyanshi_arun.

C#

// C# code to Find subarray
// with given sum
using System;
  
class GFG {
    // 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 = arr[i];
  
            // try all subarrays
            // starting with 'i'
            for (j = i + 1; j <= n; j++) {
                if (curr_sum == sum) {
                    int p = j - 1;
                    Console.Write("Sum found between "
                                  + "indexes " + i + " and " + p);
                    return 1;
                }
                if (curr_sum > sum || j == n)
                    break;
                curr_sum = curr_sum + arr[j];
            }
        }
  
        Console.Write("No subarray found");
        return 0;
    }
  
    // Driver Code
    public static void Main()
    {
        GFG arraysum = new GFG();
        int[] arr = { 15, 2, 4, 8, 9, 5, 10, 23 };
        int n = arr.Length;
        int sum = 23;
        arraysum.subArraySum(arr, n, sum);
    }
}
  
// This code has been contributed
// by nitin mittal

PHP

<?php
// A simple 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)
{
    $curr_sum; $i; $j;
  
    // Pick a starting point
    for ($i = 0; $i < $n; $i++)
    {
        $curr_sum = $arr[$i];
  
        // try all subarrays 
        // starting with 'i'
        for ($j = $i + 1; $j <= $n; $j++)
        {
            if ($curr_sum == $sum)
            {
                echo "Sum found between indexes ", $i, " and ", $j-1 ;
                return 1;
            }
            if ($curr_sum > $sum || $j == $n)
                break;
        $curr_sum = $curr_sum + $arr[$j];
        }
    }
  
    echo "No subarray found";
    return 0;
}
  
    // Driver Code
    $arr= array(15, 2, 4, 8, 9, 5, 10, 23);
    $n = sizeof($arr);
    $sum = 23;
    subArraySum($arr, $n, $sum);
    return 0;
      
// This code is contributed by AJit
?>

JavaScript

<script>
  
/* A simple 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)
{
    let curr_sum=0;
  
    // Pick a starting point
    for (let i = 0; i < n; i++) {
        curr_sum = arr[i];
  
        // try all subarrays starting with 'i'
        for (let j = i + 1; j <= n; j++) {
            if (curr_sum == sum) {
                document.write("Sum found between indexes "+i+" and "+(j - 1));
                return;
            }
            if (curr_sum > sum || j == n)
                break;
            curr_sum = curr_sum + arr[j];
        }
    }
  
    document.write("No subarray found");
    return;
}
  
// Driver Code
  
let arr= [15, 2, 4, 8, 9, 5, 10, 23];
let n = arr.length;
let sum = 23;
subArraySum(arr, n, sum);
  
</script>
Producción

Sum found between indexes 1 and 4

Análisis de Complejidad:  

  • Complejidad de tiempo: O(n^2) en el peor de los casos. 
    El bucle anidado se usa para atravesar la array, por lo que la complejidad del tiempo es O (n ^ 2)
  • Complejidad espacial: O(1). 
    Como se requiere espacio adicional constante.

Enfoque eficiente: hay una idea si todos los elementos de la array son positivos. Si un subarreglo tiene una suma mayor que la suma dada, entonces no hay posibilidad de que al agregar elementos al subarreglo actual, la suma sea x (suma dada). La idea es utilizar un enfoque similar a una ventana deslizante. Comience con un subarreglo vacío, agregue elementos al subarreglo hasta que la suma sea menor que x . Si la suma es mayor que x , elimine elementos del inicio del subarreglo actual.
Algoritmo:  

  1. Crea dos variables, l=0, suma = 0
  2. Atraviesa la array de principio a fin.
  3. Actualice la variable sum agregando el elemento actual, sum = sum + array[i]
  4. Si la suma es mayor que la suma dada, actualice la variable sum como sum = sum – array[l] y actualice l como l++.
  5. Si la suma es igual a la suma dada, imprima el subarreglo y rompa el ciclo.

C++

/* An efficient program to print 
subarray with sum as given sum */
#include <iostream>
using namespace std;
  
/* Returns true if the there is a subarray of 
arr[] with a sum equal to 'sum' otherwise 
returns false. Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
    /* Initialize curr_sum as value of 
    first element and starting point as 0 */
    int curr_sum = arr[0], start = 0, i;
  
    /* Add elements one by one to curr_sum and 
    if the curr_sum exceeds the sum,
    then remove starting element */
    for (i = 1; i <= n; i++) {
        // If curr_sum exceeds the sum,
        // then remove the starting elements
        while (curr_sum > sum && start < i - 1) {
            curr_sum = curr_sum - arr[start];
            start++;
        }
  
        // If curr_sum becomes equal to sum,
        // then return true
        if (curr_sum == sum) {
            cout << "Sum found between indexes "
                 << start << " and " << i - 1;
            return 1;
        }
  
        // Add this element to curr_sum
        if (i < n)
            curr_sum = curr_sum + arr[i];
    }
  
    // If we reach here, then no subarray
    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;
}
  
// This code is contributed by SHUBHAMSINGH10

C

/* An efficient program to print 
subarray with sum as given sum */
#include <stdio.h>
  
/* Returns true if the there is a 
subarray of arr[] with a sum 
equal to 'sum' otherwise returns 
false.  Also, prints the result */
int subArraySum(int arr[], int n, int sum)
{
    /* Initialize curr_sum as 
       value of first element and 
starting point as 0 */
    int curr_sum = arr[0], start = 0, i;
  
    /* Add elements one by one to 
curr_sum and if the curr_sum 
       exceeds the sum, then remove 
starting element */
    for (i = 1; i <= n; i++) {
        // If curr_sum exceeds the sum,
        // then remove the starting elements
        while (curr_sum > sum && start < i - 1) {
            curr_sum = curr_sum - arr[start];
            start++;
        }
  
        // If curr_sum becomes equal to sum,
        // then return true
        if (curr_sum == sum) {
            printf(
                "Sum found between indexes %d and %d",
                start, i - 1);
            return 1;
        }
  
        // Add this element to curr_sum
        if (i < n)
            curr_sum = curr_sum + arr[i];
    }
  
    // If we reach here, then no subarray
    printf("No subarray found");
    return 0;
}
  
// Driver program to test above function
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

class SubarraySum {
    /* 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 = arr[0], start = 0, i;
  
        // Pick a starting point
        for (i = 1; i <= n; i++) {
            // If curr_sum exceeds the sum,
            // then remove the starting elements
            while (curr_sum > sum && start < i - 1) {
                curr_sum = curr_sum - arr[start];
                start++;
            }
  
            // If curr_sum becomes equal to sum,
            // then return true
            if (curr_sum == sum) {
                int p = i - 1;
                System.out.println(
                    "Sum found between indexes " + start
                    + " and " + p);
                return 1;
            }
  
            // Add this element to curr_sum
            if (i < n)
                curr_sum = curr_sum + arr[i];
        }
  
        System.out.println("No subarray found");
        return 0;
    }
  
    public static void main(String[] args)
    {
        SubarraySum arraysum = new SubarraySum();
        int arr[] = { 15, 2, 4, 8, 9, 5, 10, 23 };
        int n = arr.length;
        int sum = 23;
        arraysum.subArraySum(arr, n, sum);
    }
}
  
// This code has been contributed by Mayank Jaiswal(mayank_24)

Python3

# An efficient 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_):
      
    # Initialize curr_sum as
    # value of first element
    # and starting point as 0 
    curr_sum = arr[0]
    start = 0
  
    # Add elements one by 
    # one to curr_sum and 
    # if the curr_sum exceeds 
    # the sum, then remove 
    # starting element 
    i = 1
    while i <= n:
          
        # If curr_sum exceeds
        # the sum, then remove
        # the starting elements
        while curr_sum > sum_ and start < i-1:
          
            curr_sum = curr_sum - arr[start]
            start += 1
              
        # If curr_sum becomes
        # equal to sum, then
        # return true
        if curr_sum == sum_:
            print ("Sum found between indexes")
            print ("% d and % d"%(start, i-1))
            return 1
  
        # Add this element 
        # to curr_sum
        if i < n:
            curr_sum = curr_sum + arr[i]
        i += 1
  
    # If we reach here, 
    # then no subarray
    print ("No subarray found")
    return 0
  
# Driver program
arr = [15, 2, 4, 8, 9, 5, 10, 23]
n = len(arr)
sum_ = 23
  
subArraySum(arr, n, sum_)
  
# This code is Contributed by shreyanshi_arun.

C#

// An efficient C# program to print
// subarray with sum as given sum
using System;
  
class GFG {
  
    // 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 = arr[0],
            start = 0, i;
  
        // Pick a starting point
        for (i = 1; i <= n; i++) {
            // If curr_sum exceeds
            // the sum, then remove
            // the starting elements
            while (curr_sum > sum && start < i - 1) {
                curr_sum = curr_sum - arr[start];
                start++;
            }
  
            // If curr_sum becomes equal to
            // sum, then return true
            if (curr_sum == sum) {
                int p = i - 1;
                Console.WriteLine("Sum found between "
                                  + "indexes " + start + " and " + p);
                return 1;
            }
  
            // Add this element to curr_sum
            if (i < n)
                curr_sum = curr_sum + arr[i];
        }
        Console.WriteLine("No subarray found");
        return 0;
    }
  
    // Driver code
    public static void Main()
    {
        GFG arraysum = new GFG();
        int[] arr = new int[] { 15, 2, 4, 8,
                                9, 5, 10, 23 };
        int n = arr.Length;
        int sum = 23;
        arraysum.subArraySum(arr, n, sum);
    }
}
  
// This code has been contributed by KRV.

PHP

<?php
/* An efficient 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)
{
    /* Initialize curr_sum as 
    value of first element
    and starting point as 0 */
    $curr_sum = $arr[0]; 
    $start = 0; $i;
  
    /* Add elements one by one to 
    curr_sum and if the curr_sum 
    exceeds the sum, then remove
    starting element */
    for ($i = 1; $i <= $n; $i++)
    {
        // If curr_sum exceeds the sum, 
        // then remove the starting elements
        while ($curr_sum > $sum and 
               $start < $i - 1)
        {
            $curr_sum = $curr_sum - 
                        $arr[$start];
            $start++;
        }
  
        // If curr_sum becomes equal 
        // to sum, then return true
        if ($curr_sum == $sum)
        {
            echo "Sum found between indexes",
                             " ", $start, " ", 
                           "and ", " ", $i - 1;
            return 1;
        }
  
        // Add this element
        // to curr_sum
        if ($i < $n)
        $curr_sum = $curr_sum + $arr[$i];
    }
  
    // If we reach here,
    // then no subarray
    echo "No subarray found";
    return 0;
}
  
// Driver Code
$arr = array(15, 2, 4, 8, 
              9, 5, 10, 23);
$n = count($arr);
$sum = 23;
subArraySum($arr, $n, $sum);
  
// This code has been
// contributed by anuj_67.
?>

JavaScript

<script>
/* 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)
    {
        let curr_sum = arr[0], start = 0, i;
   
        // Pick a starting point
        for (i = 1; i <= n; i++) {
            // If curr_sum exceeds the sum,
            // then remove the starting elements
            while (curr_sum > sum && start < i - 1) {
                curr_sum = curr_sum - arr[start];
                start++;
            }
   
            // If curr_sum becomes equal to sum,
            // then return true
            if (curr_sum == sum) {
                let p = i - 1;
                document.write(
                    "Sum found between indexes " + start
                    + " and " + p+"<br>");
                return 1;
            }
   
            // Add this element to curr_sum
            if (i < n)
                curr_sum = curr_sum + arr[i];
        }
   
        document.write("No subarray found");
        return 0;
    }
      
    let arr=[15, 2, 4, 8, 9, 5, 10, 23 ];
    let n = arr.length;
    let sum = 23;
    subArraySum(arr, n, sum);
      
    // This code is contributed by unknown2108
</script>
Producción

Sum found between indexes 1 and 4

Complete Interview Preparation - GFG

Análisis de Complejidad:  

  • Complejidad temporal: O(n). 
    • El Array se recorre solo una vez para insertar elementos en la ventana. Tomará tiempo O(N)
    • El Array se recorre una vez más para eliminar elementos de la ventana. También tomará tiempo O(N).
    • Entonces el tiempo total será O(N) + O(N) = O(2*N), que es similar a O(N)
  • Complejidad espacial: O(1). 
    Como se requiere espacio adicional constante.

La solución anterior no maneja números negativos. Podemos usar hashing para manejar números negativos. Vea a continuación el conjunto 2.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *