Programa Java 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.

// Java program to implement
// the above approach
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;
    }
  
    // Driver code
    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 is contributed by Mayank Jaiswal(mayank_24)

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.

// Java program to implement
// the above approach
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;
    }
  
    // Driver code
    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 is contributed by Mayank Jaiswal(mayank_24)

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!