# Java solution O(n) add, O(1) find and O(n) space

• ``````public class TwoSum {

Map<Integer, Integer> numToCountMap = new HashMap<>();
Set<Integer> sums = new HashSet<>();

for (Integer ele : numToCountMap.keySet()){
}
Integer counts = numToCountMap.get(number);
counts = (counts == null) ? 1 : counts+1;
numToCountMap.put(number, counts);
}

public boolean find(int value) {
return sums.contains(value);

}
}
``````

but I do not understand why OJ gives me a "Time Limit Exceeded". Any help will be greatly appreciated.

• later on, I did a O(1) add, O(n) find with O(n) space, the system said it is OK. just let you know

public class TwoSum {

``````Map<Integer, Integer> numToCountMap = new HashMap<>();

Integer counts = numToCountMap.get(number);
counts = (counts == null) ? 1 : counts+1;
numToCountMap.put(number, counts);
}

public boolean find(int value) {
for (Map.Entry<Integer, Integer> entry: numToCountMap.entrySet()) {
int key = entry.getKey();
int second = value - key;
int counts = entry.getValue();
if ((second == key && counts > 1 )|| (second != key) && numToCountMap.containsKey(second)) {
return true;
}
}
return false;
}
``````

}

• I think OJ has one (or more?) test case that "add()" a bunch of number but does not try to "find()". I also write an O(n)-time add() and O(1)-time find(). The code is like this

``````public:

for(const auto& num:numSet)
sumSet.insert(num+number);
numSet.insert(number);
}

bool find(int value) {
return sumSet.find(value)!=sumSet.end();
}
private:
unordered_set<int> numSet, sumSet;
``````

To see the failed case just copy and paste.

• Thanks for sharing. Btw, O(n) add and O(1) find is not exactly O(n) space, but could be O(n^2) due to the sums set.

• This post is deleted!

• I want to ask, why is O(n) space?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.