Como você encontra o número de subarrays contíguos de tamanho$k$em uma determinada matriz?
Por exemplo: Dado o array$[1,2,3,4,5,6,7,8,9]$Onde$N$é o comprimento da matriz e$k$é o tamanho do subarray. Aqui$N = 9$e dado$k = 5$, descobrimos que$N-k+1$subarrays contíguos de tamanho$k$pode ser encontrado. Como podemos provar$N-k+1$como o número de subarrays contíguos de tamanho$k$? Tenho certeza de que é intuitivo, mas não consigo entender.
Respostas
Em vez de olhar para a resposta para um valor geral de$k$, vejamos exemplos específicos.
Em primeiro lugar, quantos subarrays de comprimento um existem? A resposta a esta pergunta é$n$. Por quê? Porque podemos escolher qualquer um dos$n$elementos para estar em nossa matriz.
Em seguida, quantos subarrays de comprimento dois existem? A resposta a esta pergunta é$n - 1$. Por quê? Porque podemos escolher qualquer um dos$n$elementos, exceto para o último elemento ser o "início" da matriz (e o elemento diretamente após ele também será incluído). Observe que não podemos "iniciar" a matriz no último elemento, pois não há elemento para incluir posteriormente.
Continuando exatamente com o mesmo raciocínio, podemos ver que a resposta para subarrays de comprimento$k$devemos ser$n - (k - 1) = n - k + 1$já que podemos "iniciar" o array em qualquer lugar, exceto no último$k - 1$posições.