Bagaimana Anda menemukan jumlah subarray ukuran yang berdekatan $k$ dalam larik tertentu?
Misalnya: Diberikan array $[1,2,3,4,5,6,7,8,9]$ dimana $N$ adalah panjang dari array dan $k$adalah ukuran subarray. Sini$N = 9$ dan diberikan $k = 5$, kami menemukan itu $N-k+1$ ukuran subarray yang berdekatan $k$dapat ditemukan. Bagaimana kita bisa membuktikannya$N-k+1$ sebagai jumlah subarray ukuran yang berdekatan $k$? Saya yakin itu intuitif, tetapi saya tidak bisa membungkus kepala saya di sekitarnya.
Jawaban
Daripada melihat jawaban untuk nilai umum $k$, mari kita lihat contoh spesifiknya.
Pertama-tama, berapa banyak subarray yang panjangnya ada? Jawaban atas pertanyaan ini adalah$n$. Mengapa? Karena kita bisa memilih salah satu$n$ elemen untuk menjadi dalam array kami.
Selanjutnya, berapa banyak subarray dengan panjang dua? Jawaban atas pertanyaan ini adalah$n - 1$. Mengapa? Karena kita bisa memilih salah satu$n$elemen kecuali elemen terakhir untuk menjadi "awal" dari array (dan elemen langsung setelah itu juga akan disertakan). Perhatikan bahwa kita tidak dapat "memulai" array pada elemen terakhir karena tidak ada elemen yang akan disertakan sesudahnya.
Melanjutkan dengan alasan yang sama persis, kita dapat melihat jawaban untuk subarray panjangnya $k$ harus $n - (k - 1) = n - k + 1$ karena kita bisa "memulai" larik di mana saja kecuali yang terakhir $k - 1$ posisi.