Question

170. 两数之和 III - 数据结构设计

English Version

题目描述

设计一个接收整数流的数据结构，该数据结构支持检查是否存在两数之和等于特定值。

实现 TwoSum 类：

• TwoSum() 使用空数组初始化 TwoSum 对象
• void add(int number) 向数据结构添加一个数 number
• boolean find(int value) 寻找数据结构中是否存在一对整数，使得两数之和与给定的值相等。如果存在，返回 true ；否则，返回 false 。

 

示例：

输入：
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
输出：
[null, null, null, null, true, false]

解释：
TwoSum twoSum = new TwoSum();
twoSum.add(1);   // [] --> [1]
twoSum.add(3);   // [1] --> [1,3]
twoSum.add(5);   // [1,3] --> [1,3,5]
twoSum.find(4);  // 1 + 3 = 4，返回 true
twoSum.find(7);  // 没有两个整数加起来等于 7 ，返回 false

 

提示：

• -105 <= number <= 105
• -231 <= value <= 231 - 1
• 最多调用 104 次 add 和 find

解法

方法一：哈希表

我们用哈希表 cnt 存储数字出现的次数。

调用 add 方法时，将数字 number 的出现次数加一。

调用 find 方法时，遍历哈希表 cnt，对于每个键 x，判断 value - x 是否也是哈希表 cnt 的键，如果是，判断 x 是否等于 value - x，如果不等，说明找到了一对和为 value 的数字，返回 true；如果等，判断 x 的出现次数是否大于 1，如果大于 1，说明找到了一对和为 value 的数字，返回 true；如果小于等于 1，说明没有找到一对和为 value 的数字，继续遍历哈希表 cnt，如果遍历结束都没有找到，返回 false。

时间复杂度：

• add 方法的时间复杂度为 $O(1)$；
• find 方法的时间复杂度为 $O(n)$。

空间复杂度 $O(n)$，其中 $n$ 为哈希表 cnt 的大小。

class TwoSum:
  def __init__(self):
    self.cnt = Counter()

  def add(self, number: int) -> None:
    self.cnt[number] += 1

  def find(self, value: int) -> bool:
    for x, v in self.cnt.items():
      y = value - x
      if y in self.cnt:
        if x != y or v > 1:
          return True
    return False


# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# obj.add(number)
# param_2 = obj.find(value)

class TwoSum {
  private Map<Integer, Integer> cnt = new HashMap<>();

  public TwoSum() {
  }

  public void add(int number) {
    cnt.merge(number, 1, Integer::sum);
  }

  public boolean find(int value) {
    for (var e : cnt.entrySet()) {
      int x = e.getKey(), v = e.getValue();
      int y = value - x;
      if (cnt.containsKey(y)) {
        if (x != y || v > 1) {
          return true;
        }
      }
    }
    return false;
  }
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum obj = new TwoSum();
 * obj.add(number);
 * boolean param_2 = obj.find(value);
 */

class TwoSum {
public:
  TwoSum() {
  }

  void add(int number) {
    ++cnt[number];
  }

  bool find(int value) {
    for (auto& [x, v] : cnt) {
      long y = (long) value - x;
      if (cnt.count(y)) {
        if (x != y || v > 1) {
          return true;
        }
      }
    }
    return false;
  }

private:
  unordered_map<int, int> cnt;
};

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum* obj = new TwoSum();
 * obj->add(number);
 * bool param_2 = obj->find(value);
 */

type TwoSum struct {
  cnt map[int]int
}

func Constructor() TwoSum {
  return TwoSum{map[int]int{}}
}

func (this *TwoSum) Add(number int) {
  this.cnt[number]++
}

func (this *TwoSum) Find(value int) bool {
  for x, v := range this.cnt {
    y := value - x
    if _, ok := this.cnt[y]; ok && (x != y || v > 1) {
      return true
    }
  }
  return false
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(number);
 * param_2 := obj.Find(value);
 */