Как найти количество смежных подмассивов размера $k$ в данном массиве?
Например: учитывая массив $[1,2,3,4,5,6,7,8,9]$ где $N$ - длина массива и $k$- размер подмассива. Вот$N = 9$ и учитывая $k = 5$, мы находим, что $N-k+1$ смежные подмассивы размера $k$может быть найден. Как мы можем доказать$N-k+1$ как количество смежных подмассивов размером $k$? Я уверен, что это интуитивно понятно, но я не могу осмыслить это.
Ответы
Вместо того, чтобы искать ответ на общее значение $k$, давайте рассмотрим конкретные примеры.
Прежде всего, сколько существует подмассивов длины один? Ответ на этот вопрос$n$. Зачем? Потому что мы можем выбрать любой из$n$ элементы, которые должны быть в нашем массиве.
Далее, сколько существует подмассивов длины два? Ответ на этот вопрос$n - 1$. Зачем? Потому что мы можем выбрать любой из$n$элементы, за исключением последнего элемента, который будет «началом» массива (и элемент сразу после него также будет включен). Обратите внимание, что мы не можем «запустить» массив с последнего элемента, так как нет элемента, который можно было бы включить позже.
Продолжая те же рассуждения, мы видим, что ответ для подмассивов длины $k$ должно быть $n - (k - 1) = n - k + 1$ поскольку мы можем "запустить" массив где угодно, кроме последнего $k - 1$ позиции.