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程序：过滤具有特定配对和的行

开启你的职业生涯

完成课程获得认证
打印页面