Leetcode 170. Two Sum III - Data structure design
Problem
In this problem, we have to design a TwoSum
class. It should support two operations: add
and find
.
- The
add
method takes an integer as an input and adds it to an internal data structure. - The
find
method takes an integer as input, and it should returntrue
if there exists any pair of numbers within the internal data structure that sums to the value given tofind
method else it should returnfalse
.
For instance, if add
(1), add
(3), and add
(5) methods are called, the internal data structure contains the numbers [1, 3, 5]. Now, if find
(4) method is called, it returns true
because there exists a pair (1, 3) in the internal data structure that sums to 4.
Let's walk through this example to understand it better:
Example 1:
- Call
add
(1) -> adds 1 to the internal data structure. - Call
add
(3) -> adds 3 to the internal data structure. - Call
add
(5) -> adds 5 to the internal data structure. - Call
find
(4) -> Returnstrue
because there exists a pair (1, 3) in the internal data structure that sums to 4. - Call
find
(7) -> Returnsfalse
because there is no pair in the internal data structure that sums to 7.
Approach
The solution to this problem involves using a hash map data structure to keep track of the numbers that have been added using the add
operation. For every number added, it increments the count associated with that number in the hash map.
When the find
operation is called, it goes through every number in the hash map and calculates the remaining value which is value - number
.
- If the number itself equals the remaining value, and there are more than one of that number, that means a pair is found, and it returns
true
. - If the number does not equal the remaining value, and the remaining value is in the hash map, that means a pair is found, and it returns
true
.
Otherwise, a pair is not found and it returns false
.
Python solution
1
2python
3class TwoSum:
4 def __init__(self):
5 self.count = {}
6
7 def add(self, number: int) -> None:
8 if number in self.count:
9 self.count[number] += 1
10 else:
11 self.count[number] = 1
12
13 def find(self, value: int) -> bool:
14 for key in self.count:
15 if value-key in self.count and (value-key != key or self.count[key] > 1):
16 return True
17 return False
Java solution
1 2java 3class TwoSum { 4 private HashMap<Integer, Integer> count = new HashMap<>(); 5 6 public void add(int number) { 7 count.put(number, count.getOrDefault(number, 0) + 1); 8 } 9 10 public boolean find(int value) { 11 for (Integer key : count.keySet()) { 12 int remainder = value - key; 13 if ((key == remainder && count.get(key) > 1) || 14 (key != remainder && count.containsKey(remainder))) { 15 return true; 16 } 17 } 18 return false; 19 } 20}
Javascript solution
1 2javascript 3class TwoSum { 4 constructor() { 5 this.count = new Map(); 6 } 7 8 add(number) { 9 this.count.set(number, (this.count.get(number) || 0) + 1); 10 } 11 12 find(value) { 13 for (let [key, freq] of this.count.entries()) { 14 let remainder = value - key; 15 if ((key == remainder && freq > 1) || 16 (key != remainder && this.count.has(remainder))) { 17 return true; 18 } 19 } 20 return false; 21 } 22}
C++ solution
1 2cpp 3class TwoSum { 4public: 5 unordered_map<int, int> count; 6 7 void add(int number) { 8 count[number]++; 9 } 10 11 bool find(int value) { 12 for (auto it = count.begin(); it != count.end(); ++it) { 13 int key = it->first; 14 int remainder = value - key; 15 if ((key == remainder && it->second > 1) || 16 (key != remainder && count.count(remainder))) { 17 return true; 18 } 19 } 20 return false; 21 } 22};
C# solution
1 2csharp 3public class TwoSum { 4 private Dictionary<int, int> count = new Dictionary<int, int>(); 5 6 public void Add(int number) { 7 if (count.ContainsKey(number)) { 8 count[number]++; 9 } else { 10 count.Add(number, 1); 11 } 12 } 13 14 public bool Find(int value) { 15 foreach(var entry in count) { 16 int key = entry.Key; 17 int remainder = value - key; 18 if ((key == remainder && count[key] > 1) || 19 (key != remainder && count.ContainsKey(remainder))) { 20 return true; 21 } 22 } 23 return false; 24 } 25}
Rust solution
1
2rust
3use std::collections::HashMap;
4
5struct TwoSum {
6 count: HashMap<i32, i32>,
7}
8
9impl TwoSum {
10 pub fn new() -> Self {
11 Self {
12 count: HashMap::new(),
13 }
14 }
15
16 pub fn add(&mut self, num: i32) {
17 let counter = self.count.entry(num).or_insert(0);
18 *counter += 1;
19 }
20
21 pub fn find(&self, value: i32) -> bool {
22 for (&key, &val) in self.count.iter() {
23 let diff = value - key;
24 if (key == diff && val > 1) || (key != diff && self.count.contains_key(&diff)) {
25 return true;
26 }
27 }
28 false
29 }
30}
In this Rust solution, we utilize the HashMap data structure to count the integer numbers. The add
function increases the value of the key (which is the given number), and find
function iterates over the HashMap to find if a pair that adds up to the input exists.
Ruby solution
1 2ruby 3class TwoSum 4 attr_reader :count 5 6 def initialize 7 @count = Hash.new(0) 8 end 9 10 def add(number) 11 @count[number] += 1 12 end 13 14 def find(value) 15 @count.each do |key, _| 16 remainder = value - key 17 next if remainder == key && @count[key] < 2 18 return true if @count.key?(remainder) 19 end 20 false 21 end 22end
Here, in the Ruby solution, we also use a Hash to store the count of each number that was added. If the pair for the value is found, we return 'true'. If not, after checking all possible values, we return 'false'.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.