Programa C++ para encontrar un subarreglo con una suma dada: conjunto 1 (números no negativos)

Dado un arreglo desordenado de enteros no negativos, encuentre un subarreglo continuo que se suma a un número dado. 
Ejemplos: 

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

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

Input: arr[] = {1, 4}, sum = 0
Output: No subarray found
There is no subarray with 0 sum

Puede haber más de un subarreglo con suma como la suma dada. Las siguientes soluciones imprimen primero dicho subarreglo. 

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++ 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

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 tres 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.

/* 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

Producción :

Sum found between indexes 1 and 4

Análisis de Complejidad:  

• Complejidad temporal: O(n). 
  Solo se requiere un recorrido de la array. Entonces la complejidad del tiempo es O(n).
• Complejidad espacial: O(1). 
  Como se requiere espacio adicional constante.

Consulte el artículo completo sobre Buscar subarreglo con la suma dada | ¡Establezca 1 (Números no negativos) para obtener más detalles!