Programa de Python 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.

# Python program to implement
# the above approach
# Returns true if the there is a subarray
# of arr[] with sum equal to 'sum' otherwise 
# returns false. Also, prints the result 
def subArraySum(arr, n, sum_):
      
    # Pick a starting point
    for i in range(n):
        curr_sum = arr[i]
      
        # Try all subarrays starting 
        # with 'i'
        j = i + 1
        while j <= n:        
            if curr_sum == sum_:
                print ("Sum found between")
                print("indexes % d and % d"%( i, j-1))                
                return 1
                  
            if curr_sum > sum_ or j == n:
                break
              
            curr_sum = curr_sum + arr[j]
            j += 1
  
    print ("No subarray found")
    return 0
  
# Driver code
arr = [15, 2, 4, 8, 9, 5, 10, 23]
n = len(arr)
sum_ = 23
  
subArraySum(arr, n, sum_)
# This code is contributed by shreyanshi_arun.

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.

# 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.
def subArraySum(arr, n, sum_):
      
    # Initialize curr_sum as value of 
    # first element and starting point 
    # as 0 
    curr_sum = arr[0]
    start = 0
  
    # Add elements one by one to curr_sum 
    # and if the curr_sum exceeds the sum, 
    # then remove starting element 
    i = 1
    while i <= n:
          
        # 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 += 1
              
        # If curr_sum becomes equal to sum, 
        # then return true
        if curr_sum == sum_:
            print ("Sum found between indexes")
            print ("% d and % d"%(start, i-1))
            return 1
  
        # Add this element to curr_sum
        if i < n:
            curr_sum = curr_sum + arr[i]
        i += 1
  
    # If we reach here, then no subarray
    print ("No subarray found")
    return 0
  
# Driver code
arr = [15, 2, 4, 8, 9, 5, 10, 23]
n = len(arr)
sum_ = 23
subArraySum(arr, n, sum_)
# This code is contributed by shreyanshi_arun.

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!