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。

為了解決這個問題，我們將遵循以下步驟：

  • 定義建構函式。
  • nums := 一個新的集合
  • multiple := 一個新的集合
  • 定義一個add()函式。該函式將接收val。
    • 如果val在nums中，則
  • 將val插入到multiple中
    • 否則，
  • 將val插入到nums中
  • 定義一個find()函式。該函式將接收val。
    • 對於nums中的每個n：
      • 如果n + n等於val，則
    • 當n在multiple中時返回true
      • 否則，如果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))

讓我們來看下面的實現來更好地理解：

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

輸入

True
True
False

作者：Arnab Chakraborty

更新於：2021年10月14日

Python程式：過濾具有特定配對和的行

開啟你的職業生涯

完成課程獲得認證
列印頁面