# Question

Formatted question description: https://leetcode.ca/all/170.html


Design and implement a TwoSum class. It should support the following operations: add and find.

find - Find if there exists any pair of numbers which sum is equal to the value.

For example,
find(4) -> true
find(7) -> false


# Algorithm

HashMap to hold remainder.

Establish a mapping between each number and the number of occurrences, and then traverse the HashMap. For each value, first find the difference t between this value and the target value, and then you need to look at it in two cases.

• If the current value is not equal to the difference t, then return True as long as there is a difference t in the HashMap, or when the difference t is equal to the current value,
• If the number of mapping times of the HashMap is greater than 1, it means that there is another number in the HashMap that is equal to the current value, and the addition of the two is the target value

# Code

Java

• 
// time: O(N)
// space: O(N)
public class TwoSum {

// number to frequency
private HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

if (hm.containsKey(number)) {
hm.put(number, hm.get(number) + 1);
} else {
hm.put(number, 1);
}
}

public boolean find(int value) {
for (Integer oneNumber : hm.keySet()) {
int target = value - oneNumber;
if (hm.containsKey(target)) {
if (oneNumber == target && hm.get(target) < 2) {
continue;
}
return true;
}
}
return false;
}
}


• // OJ: https://leetcode.com/problems/two-sum-iii-data-structure-design/
// Time:
//      TwoSum: O(1)
//      find: O(NlogN)
// Space: O(N)
class TwoSum {
map<long, int> m;
public:
TwoSum() {}
m[n]++;
}
bool find(int n) {
for (auto &[a, cnt] : m) {
long b = n - a;
if (a > b) return false;
if (a == b) return cnt > 1;
if (m.count(b)) return true;
}
return false;
}
};

• class TwoSum(object):

def __init__(self):
"""
"""
self.nums = {}

"""
Add the number to an internal data structure.
:rtype: nothing
"""
self.nums[number] = self.nums.get(number, 0) + 1

def find(self, value):
"""
Find if there exists any pair of numbers which sum is equal to the value.
:type value: int
:rtype: bool
"""
d = self.nums
for num in d:
t = value - num
if t in d:
if t == num:
if d[t] >= 2:
return True
else:
return True

return False

# Your TwoSum object will be instantiated and called as such:
# twoSum = TwoSum()