ค้นหาคู่ที่มีผลรวมกำหนด
เอาชนะการค้นหาแบบตรงไปตรงมา O(n^2)
ค้นหาคู่ที่มีผลรวมกำหนด เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
ปัญหาผลรวมของคู่ค่า
เมื่อกำหนดอาร์เรย์และเป้าหมาย ให้หาค่าสองค่าที่ รวมกันแล้วได้ค่าเป้าหมาย นี่เป็นหนึ่งในโจทย์ฝึกมือที่พบบ่อยที่สุดในการแข่งขัน 🔍
วิธีลองทุกกรณี
วิธีตรงไปตรงมาคือทดลอง ทุกคู่ค่าด้วยลูปซ้อนสองชั้น วิธีนี้ใช้ได้ แต่การตรวจสอบทุกคู่มีค่าใช้จ่าย O(n^2) และอาจช้าเกินไปมาก
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return (i, j)จุดที่การลองทุกกรณีไปต่อไม่ได้
เมื่อ n ใกล้ 100000 ค่า O(n^2) หมายถึงการตรวจสอบหนึ่งหมื่นล้านครั้ง และคุณจะพบกับ TLE ข้อจำกัดกำลังบอกให้คุณหาวิธีที่เร็วกว่า
เรียงลำดับแล้วกวาดผ่าน
หากคุณ sort อาร์เรย์ก่อน ตัวชี้สองตัวจากปลายทั้งสองด้านจะช่วยแก้โจทย์ได้ในรอบเดียว การเรียงลำดับใช้เวลา O(n log n) จากนั้นการกวาดผ่านใช้เวลา O(n)
a.sort()
left, right = 0, len(a) - 1เปรียบเทียบกับเป้าหมาย
ในแต่ละขั้นตอน ให้อ่านค่า a[left] + a[right] ตัวเลขเพียงค่าเดียวนี้จะตัดสินการเลื่อนครั้งถัดไปโดยไม่ต้องเดา
total = a[left] + a[right]ตรงกันพอดี: เสร็จสิ้น
หากผลรวมเท่ากับเป้าหมาย แสดงว่าคุณ พบคู่ค่าแล้ว ให้ส่งคู่นี้กลับทันที เพราะคุณต้องการเพียงคำตอบที่ใช้ได้หนึ่งคำตอบ
if total == target:
return (left, right)หากไม่ใช่ ให้ปรับตัวชี้
หากผลรวมน้อยเกินไป ให้เลื่อนตัวชี้ด้าน ซ้ายไปทางขวา หากมากเกินไป ให้เลื่อนตัวชี้ด้านขวาไปทางซ้าย ลำดับที่เรียงไว้จะรับรองว่าการเลื่อนแต่ละครั้งช่วยให้เข้าใกล้คำตอบ
elif total < target:
left += 1
else:
right -= 1ไม่มีคู่ค่าที่ตรงกัน
หากตัวชี้ ข้ามกันโดยไม่พบคู่ที่ตรงกัน แสดงว่าไม่มีคู่ค่าที่ใช้ได้ การสิ้นสุดของลูปก็เป็นคำตอบที่สมบูรณ์ในตัวเอง
ทางเลือกด้วยเซตแฮช
หากต้องเก็บดัชนี เดิมไว้ เซตแฮชจะเหมาะกว่า โดยตรวจสอบสำหรับแต่ละค่าว่าเป้าหมายลบด้วยค่านั้นเคยพบแล้วหรือไม่
seen = set()
for x in a:
if target - x in seen:
# found
pass
seen.add(x)เลือกวิธีที่เหมาะสม
ใช้ ตัวชี้สองตัวเมื่ออาร์เรย์เรียงลำดับอยู่แล้วหรือสามารถเรียงลำดับได้ ใช้เซตแฮชเมื่อต้องการเวลา O(n) อย่างแท้จริงโดยไม่เรียงลำดับ หรือต้องเก็บดัชนีไว้
ระวังค่าเดียวกัน
หากค่าหนึ่งสามารถจับคู่กับ ตัวมันเองได้ ต้องตรวจสอบให้แน่ใจว่าดัชนีทั้งสองไม่เท่ากัน การตรวจสอบ left != right หรือ i != j อย่างรวดเร็วจะช่วยหลีกเลี่ยงข้อผิดพลาดนี้
ตรวจสอบอย่างรวดเร็ว
คุณต้องการเอาชนะวิธีลองทุกกรณีที่ใช้เวลา O(n^2) เพื่อค้นหาคู่ค่าที่รวมกันได้เป้าหมาย
สรุปทบทวน
เรียงลำดับแล้วกวาดผ่านด้วย ตัวชี้สองตัวเพื่อหาคู่ค่าที่ตรงกับเป้าหมายในเวลา O(n log n) หรือใช้เซตแฮชเพื่อให้ได้ O(n) เมื่อดัชนีมีความสำคัญ ให้เลือกตามข้อจำกัด ✅
คำถามที่พบบ่อย
บทเรียน “ค้นหาคู่ที่มีผลรวมกำหนด” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ค้นหาคู่ที่มีผลรวมกำหนด” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ค้นหาคู่ที่มีผลรวมกำหนด”
เอาชนะการค้นหาแบบตรงไปตรงมา O(n^2) คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 2 จากทั้งหมด 4 บทเรียน
บทเรียน “ค้นหาคู่ที่มีผลรวมกำหนด” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- ตัวชี้สองตัวบนอาร์เรย์ที่เรียงแล้ว
- ค้นหาคู่ที่มีผลรวมกำหนด
- ลบค่าซ้ำในตำแหน่งเดิม
- ผสานลำดับที่เรียงแล้วสองชุด