นับอาร์เรย์ย่อยที่มีผลรวมเป้าหมาย
ผสานผลรวมคำนำหน้ากับแผนที่แฮช
นับอาร์เรย์ย่อยที่มีผลรวมเป้าหมาย เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คำถามที่ยากขึ้น
ทีนี้มาดูโจทย์ที่พลิกแพลงขึ้น: จงนับจำนวนอาร์เรย์ย่อยที่มีผลรวมเท่ากับ k การตรวจสอบทุกคู่ช้าเกินไป แต่ผลรวมสะสมร่วมกับตารางแฮชช่วยแก้โจทย์นี้ได้ 🎯
ปรับมุมมองด้วยผลรวมสะสม
ผลรวมของอาร์เรย์ย่อยเท่ากับ prefix[r + 1] ลบด้วย prefix[l] ดังนั้นผลรวมที่เท่ากับ k หมายความว่าค่าผลรวมสะสมสองค่าต่างกันพอดี k
การจัดรูปสมการสำคัญ
หากผลรวมสะสมปัจจุบันคือ P คุณต้องมีผลรวมสะสมก่อนหน้าที่เท่ากับ P ลบ k การจัดรูปสมการนี้คือเคล็ดลับทั้งหมด
need = current_prefix - kนับแทนการค้นหา
แทนที่จะย้อนตรวจสอบทุกครั้ง ให้จดจำว่าค่าผลรวมสะสมแต่ละค่าเคยปรากฏกี่ครั้ง การนับสะสมช่วยตอบได้ในเวลา O(1)
ใช้ตารางความถี่
พจนานุกรมจะจับคู่ค่าผลรวมสะสมแต่ละค่ากับจำนวนครั้งที่พบ ตารางความถี่นี้เปลี่ยนการค้นหาให้กลายเป็นการนับได้ทันที
from collections import defaultdict
seen = defaultdict(int)กำหนดค่าเริ่มต้นให้ผลรวมว่าง
ก่อนเริ่มลูป ให้บันทึกว่าผลรวมสะสม 0 ปรากฏแล้วหนึ่งครั้ง ค่าเริ่มต้นนี้ทำให้นับอาร์เรย์ย่อยที่เริ่มจากดัชนี 0 ได้
seen[0] = 1ลูปเที่ยวเดียว
สำหรับสมาชิกแต่ละตัว ให้อัปเดตผลรวมสะสม เพิ่มจำนวนของค่าที่ต้องการ แล้วจึงบันทึกผลรวมสะสมปัจจุบัน การประมวลผลรอบเดียวจัดการได้ทั้งหมด
total += x
count += seen[total - k]
seen[total] += 1เหตุใดลำดับจึงสำคัญ
คุณต้องเพิ่มค่าให้คำตอบก่อนบันทึกผลรวมสะสมปัจจุบัน มิฉะนั้นช่วงที่มีความยาวเป็นศูนย์จะถูกนับเข้ามาและจำนวนจะผิดพลาด
ข้อได้เปรียบด้านความเร็ว
สมาชิกแต่ละตัวใช้เวลาคงที่ ดังนั้นการนับทั้งหมดทำงานใน O(n) ซึ่งเร็วกว่าวิธีตรวจสอบทุกกรณีในเวลา O(n ยกกำลังสอง) เมื่อข้อมูลมีขนาดใหญ่
รองรับค่าติดลบ
ต่างจากหน้าต่างเลื่อน วิธีนี้จัดการตัวเลขติดลบได้อย่างถูกต้อง เพราะผลต่างของผลรวมสะสมยังใช้ได้ไม่ว่าจะมีเครื่องหมายใด
กรณีใช้งานแบบคลาสสิก
รูปแบบนี้ใช้แก้โจทย์ชื่อดังที่ถามหาอาร์เรย์ย่อยซึ่งมีผลรวมเท่ากับ k รวมถึงรูปแบบดัดแปลงอีกมากมายในระบบตรวจคำตอบการแข่งขัน
ตรวจสอบอย่างรวดเร็ว
ผลรวมสะสมปัจจุบันของคุณคือ P และเป้าหมายคือ k
สรุป
คุณสามารถนับอาร์เรย์ย่อยที่มีผลรวมตามเป้าหมายได้ใน O(n) โดยใช้ผลรวมสะสมและตารางความถี่ กำหนดค่าเริ่มต้นให้ผลรวมสะสม 0 แล้วนับก่อนบันทึก ✅
คำถามที่พบบ่อย
บทเรียน “นับอาร์เรย์ย่อยที่มีผลรวมเป้าหมาย” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “นับอาร์เรย์ย่อยที่มีผลรวมเป้าหมาย” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ 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 ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 3 จากทั้งหมด 4 บทเรียน
บทเรียน “นับอาร์เรย์ย่อยที่มีผลรวมเป้าหมาย” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- สร้างอาร์เรย์ผลรวมคำนำหน้า
- หาผลรวมช่วงใด ๆ ด้วยการลบ
- นับอาร์เรย์ย่อยที่มีผลรวมเป้าหมาย
- อาร์เรย์ผลต่างสำหรับการอัปเดตช่วง