โจทย์ Two Sum ใน Python
ในบทเรียนนี้ คุณจะแก้โจทย์ Two Sum โดยหาสมาชิกสองตัวที่ผลบวกเท่ากับค่าที่กำหนด ด้วยการวนลิสต์เพียงรอบเดียว
บทนำ
ปัญหาที่ต้องแก้
มีลิสต์ราคากับงบประมาณ สินค้าสองชิ้นไหนที่ราคารวมเท่ากับงบพอดี การตรวจทุกคู่ใช้ได้แต่ต้องเปรียบเทียบประมาณ n² / 2 ครั้ง การจำสิ่งที่คุณเห็นแล้วทำให้ทำได้ในรอบเดียว
ลองนึกภาพแบบนี้
Two Sum เหมือนการไปซื้อของด้วยงบที่ต้องใช้ให้พอดี เห็นป้ายราคาแต่ละชิ้น เราก็คิดว่ายังขาดอีกเท่าไร แล้วเปิดดูโน้ตว่าเคยเห็นของที่ราคาเท่านั้นพอดีหรือยัง ถ้าเคยก็เจอคู่แล้ว ถ้ายังก็จดราคานี้กับตำแหน่งที่เห็นไว้ แล้วเดินต่อ
complement = target - value🤔 ราคาที่ยังขาดอยู่if complement in seen:📋 ราคานี้มีในโน้ตแล้วหรือยังreturn [seen[complement], index]🛍️ เจอคู่แล้ว: ได้ตำแหน่งของทั้งสองชิ้นseen[value] = index✍️ จดราคานี้กับตำแหน่งไว้ แล้วไปต่อโจทย์ Two Sum ถามหาตำแหน่งของตัวเลขสองตัวในลิสต์ที่บวกกันได้เป้าหมาย dictionary ของค่าที่เห็นแล้วแก้ได้ในรอบเดียว ใช้เวลา O(n)
ประเด็นสำคัญ
complement = target - valueคือค่าที่จะทำให้คู่สมบูรณ์seenจับคู่แต่ละค่าที่ไปมาแล้วกับดัชนีของมัน การค้นหาจึงเร็วif complement in seen:หาคู่จากค่าก่อนหน้าseen[value] = indexถูกเก็บหลังการตรวจ ค่าหนึ่งจึงไม่ถูกจับคู่กับตัวเอง- สำหรับ 9 ค่า 7 เจอคู่ของมันคือ 2 ที่ดัชนี 0 ได้
[0, 1]
ใช้เมื่อไร?
- หาคู่ที่มีผลรวมหรือผลต่างที่กำหนด
- เรียนรู้การแลกหน่วยความจำกับความเร็วด้วย hash table
- คำถามสัมภาษณ์ที่พบบ่อยมาก และเป็นพื้นฐานของ 3-Sum และโจทย์ที่คล้ายกัน
เมื่อไรยังไม่จำเป็น
- อินพุตที่เรียงแล้วและหน่วยความจำจำกัด: two pointer จากปลายทั้งสองไม่ใช้หน่วยความจำเพิ่ม
- คุณต้องการทุกคู่ ไม่ใช่แค่คู่เดียว: รวบรวมผลลัพธ์แทนการคืนค่าที่คู่แรก
โค้ดตัวอย่าง
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))
ผลลัพธ์จากการรัน
[0, 1]
อธิบายโค้ด
ดิกชันนารี seen บันทึกค่าที่ผ่านมาแล้วพร้อมตำแหน่ง สำหรับแต่ละสมาชิก โปรแกรมคำนวณส่วนเติมเต็ม complement = target - value แล้วตรวจว่ามีอยู่ใน seen แล้วหรือไม่ การค้นในดิกชันนารีใช้เวลา O(1) อัลกอริทึมทั้งหมดจึงทำงานใน O(n) และใช้หน่วยความจำเพิ่ม O(n)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัดเพิ่มเติม
ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก
- ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
- จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
ข้อผิดพลาดที่พบบ่อย
เก็บก่อนตรวจ
ค่าหนึ่งอาจจับคู่กับตัวเองได้ เช่น 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
โจทย์ทั้งหมด