Chương trình tạo cấu trúc dữ liệu để kiểm tra tổng cặp có giống giá trị trong Python không

Giả sử chúng ta muốn tạo một cấu trúc dữ liệu có hai phương thức -

• thêm (val), điều này sẽ thêm giá trị val vào cấu trúc dữ liệu
• find (val) điều này sẽ kiểm tra xem có hai phần tử có tổng là val hay không

Chúng tôi phải thiết kế điều này để chúng tôi có thể thu được kết quả một cách nhanh chóng. Chúng tôi sẽ không tìm kiếm các con số bất cứ lúc nào khi có truy vấn.

Vì vậy, nếu đầu vào giống như tạo một đối tượng obj và thêm một vài số 6, 14, 3, 8, 11, 15, thì hãy kiểm tra như obj.find (9), obj.find (11), obj.find (15), thì đầu ra sẽ là True, True, False vì 9 có thể được tạo thành 6 + 3, 11 có thể được tạo với 3 + 8. Bây giờ 15 có mặt trong cấu trúc dữ liệu nhưng tổng của không hai số giống như 15.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định hàm tạo.
• nums:=một tập hợp mới
• nhiều:=một tập hợp mới
• Xác định một hàm add (). Điều này sẽ mất giá trị
  • chèn val vào nhiều
• nếu không,
  • chèn val vào nums
• Xác định một hàm find (). Điều này sẽ mất giá trị
• với mỗi n trong nums, thực hiện
  • nếu n + n giống val, thì
    • trả về true khi n là bội số
  • ngược lại khi val - n ở dạng num, thì
    • trả về True
• trả về Sai

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

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

Đầu ra

True
True
False