Question

170. Two Sum III - Data structure design

中文文档

Description

Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.

Implement the TwoSum class:

• TwoSum() Initializes the TwoSum object, with an empty array initially.
• void add(int number) Adds number to the data structure.
• boolean find(int value) Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.

 

Example 1:

Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]

Explanation
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, return true
twoSum.find(7);  // No two integers sum up to 7, return false

 

Constraints:

• -105 <= number <= 105
• -231 <= value <= 231 - 1
• At most 104 calls will be made to add and find.

Solutions

Solution 1

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);
 */