170. Two Sum III - Data structure design π
DifficultyEasy
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 theTwoSumobject, with an empty array initially.void add(int number)Addsnumberto the data structure.boolean find(int value)Returnstrueif 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
104calls will be made toaddandfind.
Solutions
Solution 1: Hash Table
Thinking
Support adding numbers and querying whether two of them sum to a value. At most \(10^4\) calls. Sorting on every \(\textit{find}\) is undone by later adds. A frequency map makes \(\textit{add}\) \(O(1)\); \(\textit{find}\) tries each \(x\) and looks up \(\textit{value}-x\), requiring count at least \(2\) when \(x\) equals \(\textit{value}-x\).
We use a hash table cnt to store the count of each number.
When the \(\textit{add}\) method is called, we increment the count of the number number.
When the \(\textit{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 \(\textit{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 \(\textit{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 \(\textit{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 \(\textit{add}\) method is \(O(1)\).
- The time complexity of the \(\textit{find}\) method is \(O(n)\).
The space complexity is \(O(n)\), where \(n\) is the size of the hash table \(\textit{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 | |
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 | |