Chương trình tạo cấu trúc dữ liệu kiểm tra tổng cặp bằng giá trị cho trước Python

Thiết kế cấu trúc dữ liệu với hai phương thức:

• add(val): thêm giá trị vào cấu trúc
• find(val): kiểm tra có tồn tại hai phần tử tổng bằng val không

Ví dụ: thêm 6,14,3,8,11,15 → find(9)=True (6+3), find(11)=True (3+8), find(15)=False.

Giải thuật (Hai set: số duy nhất + số xuất hiện nhiều lần)

1. nums: set lưu các giá trị đã thêm
2. multiple: set lưu giá trị xuất hiện ≥ 2 lần
3. add(val): nếu val in nums → thêm vào multiple, ngược lại thêm vào nums
4. find(val): duyệt n in nums, nếu → kiểm tra n in multiple; nếu → True

Ví dụ triển khai

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

Đầu vào

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

Đầu ra

True True False