Programa Python3 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 python program to find if
# there is a zero sum subarray
  
  
def subArrayExists(arr, n):
    # traverse through array
    # and store prefix sums
    n_sum = 0
    s = set()
  
    for i in range(n):
        n_sum += arr[i]
  
        # If prefix sum is 0 or
        # it is already present
        if n_sum == 0 or n_sum in s:
            return True
        s.add(n_sum)
  
    return False
  
  
# Driver code
arr = [-3, 2, 3, 1, 6]
n = len(arr)
if subArrayExists(arr, n) == True:
    print("Found a sunbarray with 0 sum")
else:
    print("No Such sub array exits!")
  
# This code is contributed by Shrikant13

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.