¿Cómo encuentra el número de subarreglos contiguos de tamaño$k$en una matriz dada?
Por ejemplo: Dada la matriz$[1,2,3,4,5,6,7,8,9]$dónde$N$es la longitud de la matriz y$k$es el tamaño del subarreglo. Aquí$N = 9$y dado$k = 5$, encontramos eso$N-k+1$subarreglos contiguos de tamaño$k$puede ser encontrado. ¿Cómo podemos probar$N-k+1$como el número de subarreglos contiguos de tamaño$k$? Estoy seguro de que es intuitivo, pero no puedo entenderlo.
Respuestas
En lugar de buscar en la respuesta un valor general de$k$, veamos ejemplos específicos.
En primer lugar, ¿cuántos subarreglos de longitud uno hay? La respuesta a esta pregunta es$n$. ¿Por qué? Porque podemos elegir cualquiera de los$n$elementos para estar en nuestra matriz.
A continuación, ¿cuántos subarreglos de longitud dos hay? La respuesta a esta pregunta es$n - 1$. ¿Por qué? Porque podemos elegir cualquiera de los$n$excepto que el último elemento sea el "comienzo" de la matriz (y el elemento inmediatamente posterior también se incluirá). Tenga en cuenta que no podemos "comenzar" la matriz en el último elemento ya que no hay ningún elemento para incluir después.
Continuando con exactamente el mismo razonamiento, podemos ver que la respuesta para subarreglos de longitud$k$debe ser$n - (k - 1) = n - k + 1$ya que podemos "comenzar" la matriz en cualquier lugar excepto en el último$k - 1$posiciones.