คุณจะหาจำนวนขนาดของซับเรย์ที่อยู่ติดกันได้อย่างไร $k$ ในอาร์เรย์ที่กำหนด?

Question

ตัวอย่างเช่น: รับอาร์เรย์ $[1,2,3,4,5,6,7,8,9]$ ที่ไหน $N$ คือความยาวของอาร์เรย์และ $k$คือขนาด subarray ที่นี่$N = 9$ และให้ $k = 5$เราพบว่า $N-k+1$ ขนาด subarrays ที่อยู่ติดกัน $k$สามารถพบได้ เราจะพิสูจน์ได้อย่างไร$N-k+1$ เป็นจำนวนของขนาด subarrays ที่ต่อเนื่องกัน $k$เหรอ? ฉันแน่ใจว่ามันใช้งานง่าย แต่ฉันไม่สามารถโอบรอบมันได้

Answer 1

แทนที่จะดูคำตอบสำหรับค่าทั่วไปของ $k$มาดูตัวอย่างเฉพาะ

ก่อนอื่นมี subarrays ที่มีความยาวกี่ตัว? คำตอบสำหรับคำถามนี้คือ$n$. ทำไม? เพราะเราสามารถเลือกไฟล์$n$ องค์ประกอบที่จะอยู่ในอาร์เรย์ของเรา

ต่อไปมี subarrays ที่มีความยาวสองเท่า? คำตอบสำหรับคำถามนี้คือ$n - 1$. ทำไม? เพราะเราสามารถเลือกไฟล์$n$องค์ประกอบยกเว้นองค์ประกอบสุดท้ายที่จะเป็น "เริ่มต้น" ของอาร์เรย์ (และองค์ประกอบที่อยู่หลังจากนั้นจะรวมอยู่ด้วย) โปรดทราบว่าเราไม่สามารถ "เริ่ม" อาร์เรย์ที่องค์ประกอบสุดท้ายได้เนื่องจากไม่มีองค์ประกอบที่จะรวมในภายหลัง

ต่อด้วยเหตุผลเดียวกันเราจะเห็นว่าคำตอบสำหรับ subarrays ของความยาว $k$ ต้องเป็น $n - (k - 1) = n - k + 1$ เนื่องจากเราสามารถ "เริ่ม" อาร์เรย์ได้ทุกที่ยกเว้นรายการสุดท้าย $k - 1$ ตำแหน่ง.