โปรแกรมสร้างโครงสร้างข้อมูลตรวจสอบคู่ที่ผลรวมเท่ากับค่าที่กำหนดใน Python

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

• add(val) เพิ่มค่า val เข้าโครงสร้างข้อมูล
• find(val) ตรวจสอบว่ามีสองสมาชิกที่ผลรวมเท่ากับ 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

ขั้นตอนการแก้ปัญหา

1. กำหนด Constructor:
   • nums := เซตใหม่
   • multiple := เซตใหม่
2. กำหนดฟังก์ชัน add(val):
   • ถ้า val อยู่ใน nums เพิ่มเข้า multiple
   • มิฉะนั้น เพิ่มเข้า nums
3. กำหนดฟังก์ชัน find(val):
   • สำหรับแต่ละ n ใน nums:
     • ถ้า n + n == val คืนค่า True ถ้า n อยู่ใน multiple
     • มิฉะนั้นถ้า val - n อยู่ใน nums คืนค่า True
   • คืนค่า False

ตัวอย่างการใช้งาน

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))

อินพุต

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

เอาต์พุต

True True False