Comment trouvez-vous le nombre de sous-tableaux contigus de taille$k$dans un tableau donné ?

Question

Par exemple : étant donné le tableau$[1,2,3,4,5,6,7,8,9]$où$N$est la longueur du tableau et$k$est la taille du sous-tableau. Ici$N = 9$et donné$k = 5$, on trouve que$N-k+1$sous-tableaux contigus de taille$k$peut être trouvé. Comment pouvons-nous prouver$N-k+1$comme le nombre de sous-réseaux contigus de taille$k$? Je suis sûr que c'est intuitif, mais je n'arrive pas à comprendre.

Answer 1

Au lieu de regarder la réponse pour une valeur générale de$k$, regardons des exemples spécifiques.

Tout d'abord, combien y a-t-il de sous-réseaux de longueur un ? La réponse à cette question est$n$. Pourquoi? Parce que nous pouvons choisir n'importe lequel des$n$éléments à être dans notre tableau.

Ensuite, combien y a-t-il de sous-réseaux de longueur deux ? La réponse à cette question est$n - 1$. Pourquoi? Parce que nous pouvons choisir n'importe lequel des$n$éléments à l' exception du dernier élément qui sera le "début" du tableau (et l'élément directement après sera également inclus). Notez que nous ne pouvons pas "démarrer" le tableau au dernier élément car il n'y a pas d'élément à inclure par la suite.

En continuant avec exactement le même raisonnement, nous pouvons voir que la réponse pour les sous-tableaux de longueur$k$doit être$n - (k - 1) = n - k + 1$puisque nous pouvons "démarrer" le tableau n'importe où sauf le dernier$k - 1$postes.