Come si trova il numero di sottoarray contigui di size$k$in un dato array?

Question

Ad esempio: Dato l'array$[1,2,3,4,5,6,7,8,9]$dove$N$è la lunghezza dell'array e$k$è la dimensione del sottoarray. Qui$N = 9$e dato$k = 5$, lo troviamo$N-k+1$sottoarray contigui di dimensione$k$possono essere trovati. Come possiamo dimostrare$N-k+1$come il numero di sottoarray contigui di dimensione$k$? Sono sicuro che sia intuitivo, ma non riesco a capirlo.

Answer 1

Invece di guardare la risposta per un valore generale di$k$, diamo un'occhiata a esempi specifici.

Prima di tutto, quanti sottoarray di lunghezza uno ci sono? La risposta a questa domanda è$n$. Come mai? Perché possiamo scegliere uno qualsiasi dei$n$elementi da inserire nel nostro array.

Quindi, quanti sottoarray di lunghezza due ci sono? La risposta a questa domanda è$n - 1$. Come mai? Perché possiamo scegliere uno qualsiasi dei$n$elementi ad eccezione dell'ultimo elemento che deve essere l'"inizio" dell'array (e verrà incluso anche l'elemento subito dopo). Nota che non possiamo "iniziare" l'array dall'ultimo elemento poiché non c'è nessun elemento da includere dopo.

Continuando con lo stesso identico ragionamento, possiamo vedere che la risposta per sottoarray di lunghezza$k$deve essere$n - (k - 1) = n - k + 1$poiché siamo in grado di "avviare" l'array ovunque tranne che per l'ultimo$k - 1$posizioni.