อัลกอริทึม Two Sum ใน Python
Hash table ช่วยหลีกเลี่ยงลูปซ้อน
อัลกอริทึม Two Sum ใน Python คืออะไร?
Hash table ช่วยหลีกเลี่ยงลูปซ้อน
หาสองค่าที่รวมกันเท่ากับ target
ควรใช้เมื่อใด?
- ทำความเข้าใจอัลกอริทึมและโครงสร้างข้อมูล
- สังเกตแต่ละขั้นตอนและกรณีขอบ
- เปรียบเทียบเวลาและหน่วยความจำ
โค้ดตัวอย่าง
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))ผลลัพธ์ที่คาดหวัง
[0, 1]หลักการทำงาน
ค้นหา complement ใน O(1) ทำให้เวลารวม O(n) และหน่วยความจำ O(n)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัด
ลองเปลี่ยน input และทดสอบกรณีขอบก่อนใช้ชุดข้อมูลที่ใหญ่ขึ้น
- ทดสอบ input ว่าง หนึ่งสมาชิก และค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นตอน
- เปรียบเทียบประสิทธิภาพกับวิธีอื่น