0170. Two Sum III - Data structure design
https://leetcode.com/problems/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
.
ac
worst case is O(n) in finding as well...
class TwoSum {
private List<Integer> list;
private Map<Integer, Integer> map;
/** Initialize your data structure here. */
public TwoSum() {
list = new ArrayList<>();
map = new HashMap<>();
}
/** Add the number to an internal data structure.. */
public void add(int number) {
list.add(number);
map.put(number, map.getOrDefault(number, 0) + 1);
}
/** Find if there exists any pair of numbers which sum is equal to the value. */
public boolean find(int value) {
for (int n : list) {
int n2 = value - n;
if (n == n2 && map.get(n2) > 1 || n != n2 && map.containsKey(n2)) 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);
*/
Last updated
Was this helpful?