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 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 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;
}

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.

/* C 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 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;
}

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!