Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/170.html
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 theTwoSum
object, with an empty array initially.void add(int number)
Addsnumber
to the data structure.boolean find(int value)
Returnstrue
if there exists any pair of numbers whose sum is equal tovalue
, otherwise, it returnsfalse
.
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 toadd
andfind
.
Algorithm
HashMap
to hold remainder.
Establish a mapping between each number
and the number of occurrences
, and then traverse the HashMap. For each value, first find the difference t between this value and the target value, and then you need to look at it in two cases.
- If the current value is not equal to the difference t, then return True as long as there is a difference t in the HashMap, or when the difference t is equal to the current value,
- If the number of mapping times of the HashMap is greater than 1, it means that there is another number in the HashMap that is equal to the current value, and the addition of the two is the target value
Code
-
// time: O(N) // space: O(N) public class TwoSum { // number to frequency private HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); public void add(int number) { if (hm.containsKey(number)) { hm.put(number, hm.get(number) + 1); } else { hm.put(number, 1); } } public boolean find(int value) { for (Integer oneNumber : hm.keySet()) { int target = value - oneNumber; if (hm.containsKey(target)) { // @note: for case: add=3, add=3, target=6 if (oneNumber == target && hm.get(target) < 2) { continue; } return true; } } return false; } } ############### 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); */
-
// OJ: https://leetcode.com/problems/two-sum-iii-data-structure-design/ // Time: // TwoSum: O(1) // add: O(logN) // find: O(NlogN) // Space: O(N) class TwoSum { map<long, int> m; public: TwoSum() {} void add(int n) { m[n]++; } bool find(int n) { for (auto &[a, cnt] : m) { long b = n - a; if (a > b) return false; if (a == b) return cnt > 1; if (m.count(b)) return true; } return false; } };
-
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: # v > 1, for case: add=3, add=3, target=6 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(object): def __init__(self): """ initialize your data structure here """ self.nums = {} def add(self, number): """ Add the number to an internal data structure. :rtype: nothing """ self.nums[number] = self.nums.get(number, 0) + 1 def find(self, value): """ Find if there exists any pair of numbers which sum is equal to the value. :type value: int :rtype: bool """ d = self.nums for num in d: t = value - num if t in d: if t == num: if d[t] >= 2: return True else: return True return False # Your TwoSum object will be instantiated and called as such: # twoSum = TwoSum() # twoSum.add(number) # twoSum.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); */