148. Two Sum III - Data structure design

EasyDesign

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`.

Examples

Example 1

Input: operations = ["TwoSum","add","add","add","find","find"], args = [[],[1],[3],[5],[4],[7]]

Output: [null,null,null,null,true,false]

Explanation: After adding 1, 3 and 5, find(4) is true because 1 + 3 = 4. The possible pair sums are 4, 6 and 8, so find(7) is false.

Example 2

Input: operations = ["TwoSum","add","find"], args = [[],[0],[0]]

Output: [null,null,false]

Explanation: Only one 0 has been added, and a number cannot be paired with itself, so 0 + 0 is not available.

Example 3

Input: operations = ["TwoSum","add","add","find"], args = [[],[3],[3],[6]]

Output: [null,null,null,true]

Explanation: Two separate 3s have been added, so they can pair up: 3 + 3 = 6.

Constraints

-10^5 <= number <= 10^5
-2^31 <= value <= 2^31 - 1
At most 10^4 calls will be made to add and find.

How to solve Two Sum III - Data structure design: approach and complexity

Count map, O(1) add and O(n) find: O(n) find time, O(n) space.

Keep a multiplicity map of the numbers seen. add is O(1). For find(value), scan each stored number x and check whether its complement value-x is also present — with a special case when x equals the complement (need at least two copies).

Watch it run step by step