อัลกอริทึม Python

โจทย์ Two Sum ใน Python

ในบทเรียนนี้ คุณจะแก้โจทย์ Two Sum โดยหาสมาชิกสองตัวที่ผลบวกเท่ากับค่าที่กำหนด ด้วยการวนลิสต์เพียงรอบเดียว

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง

บทนำ

ปัญหาที่ต้องแก้

มีลิสต์ราคากับงบประมาณ สินค้าสองชิ้นไหนที่ราคารวมเท่ากับงบพอดี การตรวจทุกคู่ใช้ได้แต่ต้องเปรียบเทียบประมาณ n² / 2 ครั้ง การจำสิ่งที่คุณเห็นแล้วทำให้ทำได้ในรอบเดียว

ลองนึกภาพแบบนี้

Two Sum เหมือนการไปซื้อของด้วยงบที่ต้องใช้ให้พอดี เห็นป้ายราคาแต่ละชิ้น เราก็คิดว่ายังขาดอีกเท่าไร แล้วเปิดดูโน้ตว่าเคยเห็นของที่ราคาเท่านั้นพอดีหรือยัง ถ้าเคยก็เจอคู่แล้ว ถ้ายังก็จดราคานี้กับตำแหน่งที่เห็นไว้ แล้วเดินต่อ

จากการซื้อของตามงบสู่โค้ด
complement = target - value🤔 ราคาที่ยังขาดอยู่
if complement in seen:📋 ราคานี้มีในโน้ตแล้วหรือยัง
return [seen[complement], index]🛍️ เจอคู่แล้ว: ได้ตำแหน่งของทั้งสองชิ้น
seen[value] = index✍️ จดราคานี้กับตำแหน่งไว้ แล้วไปต่อ
เปิดหาราคาที่ขาดในโน้ต แทนการลองจับคู่ทุกคู่
สรุปในประโยคเดียว

โจทย์ Two Sum ถามหาตำแหน่งของตัวเลขสองตัวในลิสต์ที่บวกกันได้เป้าหมาย dictionary ของค่าที่เห็นแล้วแก้ได้ในรอบเดียว ใช้เวลา O(n)

ประเด็นสำคัญ

  1. complement = target - value คือค่าที่จะทำให้คู่สมบูรณ์
  2. seen จับคู่แต่ละค่าที่ไปมาแล้วกับดัชนีของมัน การค้นหาจึงเร็ว
  3. if complement in seen: หาคู่จากค่าก่อนหน้า
  4. seen[value] = index ถูกเก็บหลังการตรวจ ค่าหนึ่งจึงไม่ถูกจับคู่กับตัวเอง
  5. สำหรับ 9 ค่า 7 เจอคู่ของมันคือ 2 ที่ดัชนี 0 ได้ [0, 1]

ใช้เมื่อไร?

  • หาคู่ที่มีผลรวมหรือผลต่างที่กำหนด
  • เรียนรู้การแลกหน่วยความจำกับความเร็วด้วย hash table
  • คำถามสัมภาษณ์ที่พบบ่อยมาก และเป็นพื้นฐานของ 3-Sum และโจทย์ที่คล้ายกัน

เมื่อไรยังไม่จำเป็น

  • อินพุตที่เรียงแล้วและหน่วยความจำจำกัด: two pointer จากปลายทั้งสองไม่ใช้หน่วยความจำเพิ่ม
  • คุณต้องการทุกคู่ ไม่ใช่แค่คู่เดียว: รวบรวมผลลัพธ์แทนการคืนค่าที่คู่แรก

โค้ดตัวอย่าง

รันโค้ด →
main.py
def two_sum(values, target):
    seen = {}
    for index, value in enumerate(values):
        complement = target - value
        if complement in seen:
            return [seen[complement], index]
        seen[value] = index
    return []

print(two_sum([2, 7, 11, 15], 9))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

[0, 1]

อธิบายโค้ด

ดิกชันนารี seen บันทึกค่าที่ผ่านมาแล้วพร้อมตำแหน่ง สำหรับแต่ละสมาชิก โปรแกรมคำนวณส่วนเติมเต็ม complement = target - value แล้วตรวจว่ามีอยู่ใน seen แล้วหรือไม่ การค้นในดิกชันนารีใช้เวลา O(1) อัลกอริทึมทั้งหมดจึงทำงานใน O(n) และใช้หน่วยความจำเพิ่ม O(n)

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

ข้อผิดพลาดที่พบบ่อย

เก็บก่อนตรวจ

ค่าหนึ่งอาจจับคู่กับตัวเองได้ เช่น 3 + 3 = 6 ทั้งที่มี 3 แค่ตัวเดียว

ปัญหา
seen[value] = index
if target - value in seen:
วิธีแก้
if target - value in seen:
    return [seen[target - value], index]
seen[value] = index

เรียนบทนี้จบแล้วใช่ไหม

ทำเครื่องหมายว่าเรียนแล้วเพื่อติดตามความคืบหน้า

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด