サイズの連続するサブ配列の数をどのように見つけますか $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$ 位置。