Programa Php para encontrar subarreglo con 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.

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

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.

<?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 is contributed by anuj_67.
?>

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!