Número de subarreglos que contienen la longitud de ese subarreglo

/ Python / Por

Dada una matriz A[] de longitud nortela tarea es contar el número de subarreglos de A[] que contiene la longitud de ese subarreglo.

Ejemplos:

Aporte: A = {10, 11, 1}, N = 3
Salida: 1
Explicación: Solo el subarreglo {1}, con longitud 1, contiene su propia longitud.

Aporte: un = [1, 2, 3, 4, 5]norte = 5
Salida: 9
Explicación: Los subarreglos {1}, {1, 2}, {2, 3}, {1, 2, 3}, {2, 3, 4}, {3, 4, 5},
{1, 2, 3, 4}, {2, 3, 4, 5}, {1, 2, 3, 4, 5} contienen su propia longitud.

Acercarse: Siga la siguiente idea para resolver el problema:

Primero forme cada subarreglo de A. Luego verifique si la longitud del subarreglo está presente en ese subarreglo.

Siga los pasos a continuación para implementar la idea:

  • Repita la matriz de yo = 0 a N†
    • Iterando en un bucle anidado de j = yo a norte†
    • El subarreglo creado es de yo para ti†
    • Vaya a través del subarreglo y verifique si la longitud está presente en el subarreglo.
    • Si está presente, aumente la contar†
  • El último contar es la respuesta requerida.

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

Python3

 

def findCount(arr, N):

    counts = 0

     

    

    for i in range(N):

        for j in range(i + 1, N + 1):

           

            

            

            if j - i in arr[i: j]:

                counts += 1

    return counts

 

 

if __name__ == '__main__':

    arr = [1, 2, 3, 4, 5]

    N = 5

     

    

    print(findCount(arr, N))

Complejidad del tiempo: A3†
cuarto auxiliar: O(1)

Su Calificación Nos Ayuda a Mejorar