สร้างอาร์เรย์ผลรวมคำนำหน้า
คำนวณยอดสะสมล่วงหน้าเพียงครั้งเดียว
สร้างอาร์เรย์ผลรวมคำนำหน้า เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
ปัญหาผลรวมซ้ำหลายครั้ง
ลองนึกภาพว่าต้องตอบคำถามผลรวมของช่วงหลายร้อยคำถามบนอาร์เรย์เดียว การหาผลรวมของแต่ละช่วงใหม่ตั้งแต่ต้นนั้นช้า ผลรวมคำนำหน้าช่วยแก้ปัญหานี้ได้ 🚀
ผลรวมคำนำหน้าคืออะไร
อาร์เรย์ ผลรวมคำนำหน้าจะเก็บผลรวมของสมาชิกทั้งหมดตั้งแต่ต้นจนถึงแต่ละดัชนี การคำนวณล่วงหน้าเพียงรอบเดียวจะเปลี่ยนการหาผลรวมที่ช้าให้กลายเป็นคำตอบที่ได้ทันที
ตัวอย่างเล็ก ๆ
สำหรับ [3, 1, 4] ผลรวมสะสมคือ 3 จากนั้นเป็น 4 และสุดท้ายเป็น 8 รายการ ผลรวมสะสมที่เพิ่มขึ้นนี้ก็คือผลรวมคำนำหน้าของคุณ
สูตรเวียนเกิดหลัก
สมาชิกแต่ละตำแหน่งคือผลรวมก่อนหน้าบวกกับสมาชิกปัจจุบัน สูตรเวียนเกิดเพียงบรรทัดเดียวนี้เป็นหัวใจของเทคนิคทั้งหมด
prefix[i] = prefix[i - 1] + a[i]สร้างในโค้ด
เดินผ่านอาร์เรย์หนึ่งครั้งพร้อมเก็บผลรวมสะสมไว้ ในแต่ละขั้นตอนให้เพิ่มผลรวมใหม่เข้าไป ดังนั้นการสร้างอาร์เรย์จึงเป็นการประมวลผล เชิงเส้นเพียงรอบเดียว
prefix = [0]
for x in a:
prefix.append(prefix[-1] + x)เหตุผลที่ศูนย์นำหน้าช่วยได้
การเริ่มต้น prefix ด้วย ศูนย์นำหน้าหมายความว่า prefix[i] จะเก็บผลรวมของสมาชิก i ตัวแรก ทำให้การคำนวณผลรวมช่วงในภายหลังทำได้อย่างเป็นระเบียบ
หลักเกณฑ์ของดัชนี
เมื่อมีศูนย์อยู่ด้านหน้า prefix[k] จะเท่ากับ a[0] + ... + a[k-1] การยึด หลักเกณฑ์นี้ให้ถูกต้องจะช่วยป้องกันข้อผิดพลาดที่ตำแหน่งคลาดไปหนึ่งตำแหน่ง
ค่าใช้จ่ายในการสร้าง
การสร้างอาร์เรย์ผลรวมคำนำหน้าจะเข้าถึงสมาชิกแต่ละตัวเพียงครั้งเดียว จึงใช้เวลา O(n) คุณจ่ายต้นทุนนี้ครั้งเดียว แล้วนำผลลัพธ์กลับมาใช้ซ้ำได้ตลอด
คำนวณล่วงหน้าครั้งเดียว ใช้ตอบคำถามได้บ่อยครั้ง
ข้อดีสำคัญคือ การแลกเปลี่ยนนี้ คุณใช้เวลาหนึ่งรอบแบบเชิงเส้นล่วงหน้า เพื่อให้การถามผลรวมแต่ละครั้งภายหลังกลายเป็นการค้นค่าอย่างรวดเร็วแทนการใช้ลูป
ทางลัดแบบไพธอน
คลังมาตรฐานสามารถสร้างผลรวมให้คุณได้ itertools.accumulate จะสร้างผลรวมสะสมด้วยการเรียกใช้ที่กระชับเพียงครั้งเดียว
from itertools import accumulate
prefix = [0] + list(accumulate(a))ระวังการใช้หน่วยความจำ
อาร์เรย์ผลรวมคำนำหน้ามีความยาวเท่ากับข้อมูลขาเข้าบวกหนึ่ง สำหรับข้อมูลขนาดใหญ่ โปรดจำไว้ว่ามันทำให้การใช้ หน่วยความจำของคุณเพิ่มขึ้นเกือบสองเท่า
ตรวจสอบอย่างรวดเร็ว
คุณสร้างอาร์เรย์ผลรวมคำนำหน้า โดยทั่วไปดัชนี 0 จะเก็บอะไรไว้
สรุปทบทวน
คุณได้เรียนรู้การสร้างอาร์เรย์ ผลรวมคำนำหน้าในรอบเดียวที่ใช้เวลา 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 ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “สร้างอาร์เรย์ผลรวมคำนำหน้า” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- สร้างอาร์เรย์ผลรวมคำนำหน้า
- หาผลรวมช่วงใด ๆ ด้วยการลบ
- นับอาร์เรย์ย่อยที่มีผลรวมเป้าหมาย
- อาร์เรย์ผลต่างสำหรับการอัปเดตช่วง