โปรแกรมสร้างโครงสร้างข้อมูลเช็คคู่ผลรวมเท่ากับค่าใน Python

สมมติว่าเราต้องการสร้างโครงสร้างข้อมูลที่มีสองวิธี -

• add(val) เป็นการเพิ่มค่า val ให้กับโครงสร้างข้อมูล
• find(val) ใช้สำหรับตรวจสอบว่ามีองค์ประกอบ 2 ตัวที่ผลรวมเป็น val หรือไม่

เราต้องออกแบบสิ่งนี้เพื่อให้ได้ผลลัพธ์ในทันที เราจะไม่ค้นหาตัวเลขทุกครั้งที่มีการสอบถาม

ดังนั้นหากอินพุตเป็นเหมือนสร้างวัตถุ obj และเพิ่มตัวเลข 6, 14, 3, 8, 11, 15 ให้ตรวจสอบเหมือน obj.find(9), obj.find(11), obj.find(15) จากนั้นผลลัพธ์จะเป็น True, True, False เนื่องจาก 9 สามารถเกิดขึ้นได้กับ 6+3, 11 สามารถเกิดขึ้นได้ด้วย 3+8 ขณะนี้มี 15 อยู่ในโครงสร้างข้อมูล แต่ไม่มีผลรวมของตัวเลขใดเท่ากับ 15

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดคอนสตรัคเตอร์
• nums :=ชุดใหม่
• หลายชุด :=ชุดใหม่
• กำหนดฟังก์ชัน add() นี่จะใช้เวลา val
  • ใส่ค่า val ลงในตัวคูณ
• มิฉะนั้น
  • ใส่ค่า val ลงใน nums
• กำหนดฟังก์ชัน find() นี่จะใช้เวลา val
• สำหรับแต่ละ n เป็น nums ทำ
  • ถ้า n + n เหมือนกับ val แล้ว
    • คืนค่าเป็นจริงเมื่อ n อยู่ในหลาย ๆ
  • มิฉะนั้น เมื่อ val - n เป็น nums แล้ว
    • คืนค่า True
• คืนค่าเท็จ

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

class PairSumChecker:
   def __init__(self):
      self.nums = set()
      self.multiple = set()

   def add(self, val):
      if val in self.nums:
         self.multiple.add(val)
      else:
         self.nums.add(val)

   def find(self, val):
      for n in self.nums:
         if n + n == val:
            return n in self.multiple
         elif val - n in self.nums:
            return True
      return False

obj = PairSumChecker()
obj.add(6)
obj.add(14)
obj.add(3)
obj.add(8)
obj.add(11)
obj.add(15)

print(obj.find(9))
print(obj.find(11))
print(obj.find(15))

อินพุต

print(obj.find(9))
print(obj.find(11))
print(obj.find(15))

ผลลัพธ์

True
True
False