หน้าต่างแปรผันด้วยตัวชี้สองตัว
ขยายและหดเพื่อให้ตรงตามเงื่อนไข
หน้าต่างแปรผันด้วยตัวชี้สองตัว เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
เมื่อหน้าต่างขยายและหดตัว
โจทย์บางข้อไม่ได้กำหนดความยาวหน้าต่างไว้ตายตัว แต่ให้หน้าต่าง ขยายและหดตัว เพื่อรักษาเงื่อนไขให้เป็นจริง เช่น ให้ผลรวมไม่เกินขีดจำกัด
ตัวชี้สองตัว หน้าต่างเดียว
ใช้ดัชนีสองตัวคือ left และ right เพื่อระบุขอบของหน้าต่าง ตัวชี้ right จะขยายหน้าต่าง ขณะที่ left จะตามอยู่ด้านหลังและเลื่อนเพื่อหดหน้าต่างเมื่อจำเป็น
left = 0
window = 0ขยายไปทางขวา
เลื่อน right ผ่านสมาชิกทุกตัวและ รวมสมาชิกนั้นไว้ในหน้าต่าง พร้อมอัปเดตสถานะสะสม เช่น เพิ่มค่าใหม่เข้าไปในผลรวม
for right in range(n):
window += a[right]หดตัวเมื่อจำเป็น
ขณะที่หน้าต่าง ละเมิดกฎ ให้เลื่อน left ไปทางขวาและนำสมาชิกนั้นออก วิธีนี้จะทำให้เงื่อนไขกลับมาเป็นจริงโดยไม่ต้องย้อนกลับ
while window > limit:
window -= a[left]
left += 1อ่านค่าหน้าต่างที่ถูกต้อง
เมื่อจบลูปด้านใน หน้าต่างตั้งแต่ left ถึง right จะ ถูกต้อง ความยาวของหน้าต่างคือ right ลบ left บวกหนึ่ง และพร้อมนำไปใช้งาน
length = right - left + 1บันทึกค่าที่ดีที่สุด
อัปเดตคำตอบด้วยหน้าต่างที่ถูกต้องนี้ ซึ่งมักเป็นหน้าต่างที่ ยาวที่สุดที่พบ ทำเช่นนี้ในทุกครั้งที่วนซ้ำเพื่อไม่ให้พลาดหน้าต่างใดไป
best = max(best, right - left + 1)เหตุใดจึงเป็นเชิงเส้น
ตัวชี้แต่ละตัวเคลื่อนไปข้างหน้า เท่านั้นและไม่ย้อนกลับ ดังนั้น left และ right รวมกันจะเคลื่อนไหวไม่เกิน n ขั้น ทำให้การกวาดผ่านทั้งหมดใช้เวลา O(n)
ข้อกำหนดแบบโมโนโทนิก
วิธีนี้ใช้ได้เมื่อการขยายหน้าต่างทำให้เงื่อนไข ทำได้ยากขึ้นเท่านั้น พฤติกรรมแบบโมโนโทนิกนี้ทำให้ left ไม่จำเป็นต้องย้อนกลับ
ยาวที่สุดกับสั้นที่สุด
หากต้องการหน้าต่างที่ถูกต้องและ สั้นที่สุด ให้หดหน้าต่างตราบใดที่กฎยังเป็นจริง และบันทึกค่าก่อนที่เงื่อนไขจะไม่เป็นจริง กลไกของตัวชี้ยังคงเหมือนเดิม
while window >= target:
best = min(best, right - left + 1)
window -= a[left]
left += 1ระวังหน้าต่างว่าง
หากการหดหน้าต่างอาจทำให้หน้าต่างว่าง ให้ป้องกันกรณีที่ left เลย right นอกจากนี้ต้องตรวจสอบด้วยว่าพบคำตอบจริงก่อนคืนค่า
สังเกตรูปแบบ
เลือกใช้หน้าต่างแบบปรับได้เมื่อโจทย์ถามหาช่วงที่ ต่อเนื่องกันและยาวที่สุดหรือสั้นที่สุด โดยสมาชิกในช่วงต้องเป็นไปตามเงื่อนไข
ตรวจสอบอย่างรวดเร็ว
คุณใช้หน้าต่างแบบปรับได้ที่มีตัวชี้สองตัวกับอาร์เรย์ขนาด n
ทบทวน
ขยาย right เพื่อรวมสมาชิก หด left ขณะที่กฎไม่เป็นจริง และบันทึกหน้าต่างที่ถูกต้องแต่ละหน้าต่าง ตัวชี้ที่เคลื่อนไปข้างหน้าเท่านั้นทำให้วิธีนี้มีความซับซ้อน O(n) ✅
คำถามที่พบบ่อย
บทเรียน “หน้าต่างแปรผันด้วยตัวชี้สองตัว” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “หน้าต่างแปรผันด้วยตัวชี้สองตัว” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “หน้าต่างแปรผันด้วยตัวชี้สองตัว”
ขยายและหดเพื่อให้ตรงตามเงื่อนไข คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “หน้าต่างแปรผันด้วยตัวชี้สองตัว” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- ผลรวมหน้าต่างขนาดคงที่
- หน้าต่างแปรผันด้วยตัวชี้สองตัว
- สตริงย่อยที่ยาวที่สุดโดยไม่มีตัวซ้ำ
- นับหน้าต่างที่เป็นไปตามกฎ