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 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
.
Solutions
Solution 1: Hash Table
We use a hash table cnt
to store the count of each number.
When the add
method is called, we increment the count of the number number
.
When the find
method is called, we iterate over the hash table cnt
. For each key x
, we check if value - x
is also a key in the hash table cnt
. If it is, we check if x
is equal to value - x
. If they are not equal, it means we have found a pair of numbers whose sum is value
, and we return true
. If they are equal, we check if the count of x
is greater than 1
. If it is, it means we have found a pair of numbers whose sum is value
, and we return true
. If it is less than or equal to 1
, it means we have not found a pair of numbers whose sum is value
, and we continue to iterate over the hash table cnt
. If we have not found a pair after the iteration, we return false
.
Time complexity:
- The time complexity of the
add
method is $O(1)$. - The time complexity of the
find
method is $O(n)$.
Space complexity is $O(n)$, where $n$ is the size of the hash table cnt
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
|