Skip to content

170. Two Sum III - Data structure design

  • Time:
  • Space:
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class TwoSum {
 public:
  void add(int number) {
    ++count[number];
  }

  bool find(int value) {
    for (const auto& [key, freq] : count) {
      const int remain = value - key;
      if (key == remain && freq > 1)
        return true;
      if (key != remain && count.count(remain))
        return true;
    }

    return false;
  }

 private:
  unordered_map<int, int> count;
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class TwoSum {
  public void add(int number) {
    count.put(number, count.getOrDefault(number, 0) + 1);
  }

  public boolean find(int value) {
    for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
      final int key = entry.getKey();
      final int remain = value - key;
      if (key == remain && entry.getValue() > 1)
        return true;
      if (key != remain && count.containsKey(remain))
        return true;
    }

    return false;
  }

  private HashMap<Integer, Integer> count = new HashMap<>();
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class TwoSum:
  def __init__(self):
    self.count = Counter()

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

  def find(self, value: int) -> bool:
    for key, freq in self.count.items():
      remain = value - key
      if key == remain and freq > 1:
        return True
      if key != remain and remain in self.count:
        return True

    return False