Programa Java para encontrar si hay un subarreglo con 0 suma

Dada una array de números positivos y negativos, encuentre si hay una subarreglo (de tamaño al menos uno) con suma 0.

Ejemplos: 

Entrada: {4, 2, -3, 1, 6}
Salida: verdadero 
Explicación:
Hay un subarreglo con suma cero del índice 1 al 3.

Entrada: {4, 2, 0, 1, 6}
Salida : verdadero 
Explicación:
Hay un subarreglo con suma cero del índice 2 al 2.

Entrada: {-3, 2, 3, 1, 6}
Salida: falso

Una solución simple es considerar todos los subarreglos uno por uno y verificar la suma de cada subarreglo. Podemos ejecutar dos bucles: el bucle exterior elige un punto de inicio i y el bucle interior prueba todos los subarreglos a partir de i (ver esto para la implementación). La complejidad temporal de este método es O(n ² ).
También podemos usar hash . La idea es iterar a través de la array y para cada elemento arr[i], calcular la suma de los elementos de 0 a i (esto se puede hacer simplemente como sum += arr[i]). Si la suma actual se ha visto antes, entonces hay una array de suma cero. Hashing se utiliza para almacenar los valores de la suma para que podamos almacenar rápidamente la suma y averiguar si la suma actual se ve antes o no.
Ejemplo :

arr[] = {1, 4, -2, -2, 5, -4, 3}

If we consider all prefix sums, we can
notice that there is a subarray with 0
sum when :
1) Either a prefix sum repeats or
2) Or prefix sum becomes 0.

Prefix sums for above array are:
1, 5, 3, 1, 6, 2, 5

Since prefix sum 1 repeats, we have a subarray
with 0 sum. 

A continuación se muestra la implementación del enfoque anterior. 

// A Java program to find 
// if there is a zero sum subarray
import java.util.HashSet;
import java.util.Set;
  
class ZeroSumSubarray 
{
    // Returns true if arr[] 
    // has a subarray with sero sum
    static Boolean subArrayExists(int arr[])
    {
        // Creates an empty hashset hs
        Set<Integer> hs = new HashSet<Integer>();
  
        // Initialize sum of elements
        int sum = 0;
  
        // Traverse through the given array
        for (int i = 0; i < arr.length; i++) 
        {
            // Add current element to sum
            sum += arr[i];
  
            // Return true in following cases
            // a) Current element is 0
            // b) sum of elements from 0 to i is 0
            // c) sum is already present in hash map
            if (arr[i] == 0 
                || sum == 0 
                || hs.contains(sum))
                return true;
  
            // Add sum to hash set
            hs.add(sum);
        }
  
        // We reach here only when there is
        // no subarray with 0 sum
        return false;
    }
  
    // Driver code
    public static void main(String arg[])
    {
        int arr[] = { -3, 2, 3, 1, 6 };
        if (subArrayExists(arr))
            System.out.println(
                "Found a subarray with 0 sum");
        else
            System.out.println("No Such Sub Array Exists!");
    }
}

No Such Sub Array Exists!

La complejidad temporal de esta solución se puede considerar como O(n) bajo el supuesto de que tenemos una buena función hash que permite operaciones de inserción y recuperación en tiempo O(1). 
Complejidad espacial : O (n). Aquí requerimos espacio adicional para unordered_set para insertar elementos de array.
 

Consulte el artículo completo sobre Buscar si hay un subarreglo con suma 0 para obtener más detalles.