Programa de Python para encontrar el número de m elementos contiguos de una Lista con una suma dada

Dada una lista ‘L’, una suma ‘S’ y número de elementos a tomar en un tiempo ‘m’. La tarea es encontrar de cuántas maneras se pueden encontrar sumas sumando cualquier m elementos contiguos. Ejemplos:

Input : 
1 2 1 3 2
3 2

Output :
2
Input :
1 1 1 1 1 1
3 2
Output :
0

Para el ejemplo 1, tenemos que encontrar una suma 3 con la ayuda de 2 elementos contiguos cualesquiera de la lista. Esto se puede hacer de dos maneras, 1+2 y 2+1, por lo que la respuesta es 2 Método 1: (Simple) Comenzando desde el principio, seleccionamos los primeros m elementos y encontramos su suma si suma = s, luego incrementamos el conteo en uno e incrementamos el índice posición por uno, seleccione los siguientes m elementos y repita lo mismo hasta que se cubra toda la lista. 

# Python program to find number of
# m contiguous elements of a list
# with sum s
 
 
def SearchWay(l, s, m):
     
    # initialise sum and
    # count to 0
    sum1 = 0
    count = 0
     
    # iterate from start of
    # list to end
    for i in range (len(l)-m + 1):
     
        # get sum f m elements
        # starting from index i
        for j in range (i, i + m):
            sum1 += l[j]
     
        # if the sum of elements equal
        # s increment count
        if sum1 == s:
            count += 1
         
        sum1 = 0
 
    return count
 
# Driver's code
l = [1, 2, 1, 3, 2]
s = 3
m = 2
 
ans = SearchWay(l, s, m)
print(ans)

Producción:

2

Complejidad de tiempo: O(n^2) en el peor de los casos. Método 2: (Eficiente) Inicialice un índice variable como 0 y curr_sum como el primer elemento. index indica el recuento de elementos contiguos y curr_sum indica la suma de los elementos de índice actuales. Comience desde el segundo elemento y agregue todos los elementos uno por uno a curr_sum. Si curr_sum se vuelve igual a la suma y el índice se vuelve igual a m, entonces incremente el valor de cuenta en 1. Si el índice excede la m, entonces elimine los elementos finales e inicialice el índice como m-1. 

# Python program to find number of
# m contiguous elements of a list
# with sum s
 
 
def SearchWay(l, s, m):
     
    n = len(l)
         
    # Initialize curr_sum as
    # value of first element
    # and starting point as 0
    count = start = 0
    curr_sum = l[0]
     
    # Initialize the index as 1
    index = 1
 
    # Add elements one by 
    # one to curr_sum and 
    # if the index exceeds 
    # the m, then remove 
    # starting element
    # and change the value
    # of index as m-1
    i = 1
    while i <= n:
         
        # If curr_sum becomes
        # equal to sum, then
        # increment count by 1
        if curr_sum == s and index == m:
            count += 1
             
        # If index exceeds
        # the m, then remove
        # the starting elements
        while index >= m:
            curr_sum -= l[start]
            start += 1
            index = m-1
         
        # Add this element 
        # to curr_sum and
        # increment index
        if i < n:
            curr_sum += l[i]
            index += 1
        i += 1
         
    return count
 
# Driver's code
l = [1, 2, 1, 3, 2]
s = 3
m = 2
 
ans = SearchWay(l, s, m)
print(ans)

Producción:

2

La complejidad de tiempo del método 2 parece más que O(n), pero si observamos más de cerca el programa, podemos determinar que la complejidad de tiempo es O(n). Podemos probarlo contando el número de operaciones realizadas en cada elemento de arr[] en el peor de los casos. Hay como máximo 2 operaciones realizadas en cada elemento: (a) el elemento se agrega a curr_sum (b) el elemento se resta de curr_sum. Entonces, el límite superior del número de operaciones es 2n, que es O(n).