인접한 크기의 하위 배열의 수를 어떻게 찾습니까? $k$ 주어진 배열에서?

Question

예 : 주어진 배열 $[1,2,3,4,5,6,7,8,9]$ 어디 $N$ 배열의 길이이고 $k$부분 배열 크기입니다. 여기$N = 9$ 그리고 주어진 $k = 5$, 우리는 $N-k+1$ 인접한 크기의 하위 배열 $k$찾을수있다. 증명할 수있는 방법$N-k+1$ 크기의 연속 된 부분 배열의 수로 $k$? 직관적이라고 확신하지만 머리를 감쌀 수는 없습니다.

Answer 1

일반적인 가치에 대한 답을 보는 대신 $k$, 구체적인 예를 살펴 보겠습니다.

우선, 길이가 1 인 하위 배열이 몇 개 있습니까? 이 질문에 대한 대답은$n$. 왜? 우리가 선택할 수 있기 때문에$n$ 배열에있는 요소입니다.

다음으로 길이가 2 인 부분 배열이 몇 개 있습니까? 이 질문에 대한 대답은$n - 1$. 왜? 우리가 선택할 수 있기 때문에$n$요소 를 제외한 마지막 요소 어레이 (및도 포함한다 직후 소자)의 "시작"는되기를. 나중에 포함 할 요소가 없기 때문에 마지막 요소에서 배열을 "시작"할 수 없습니다.

똑같은 추론을 계속하면 길이 하위 배열에 대한 답이 $k$ 반드시 $n - (k - 1) = n - k + 1$ 마지막을 제외한 모든 곳에서 어레이를 "시작"할 수 있기 때문에 $k - 1$ 위치.