Use HashSet, it cost O(1) space.
Then loop the numbers
If it's in the set, return that number;
else, add it into the set.
My Java code takes only 8ms to complete all the test cases.
It should be a simple question.
Did you really understand this problem?
The following is the request for this Alogrithm:
You must use only constant, O(1) extra space.
From other aspect, he may be right. Say if we create a bitmap whose length is 2^64-1(constant, O(1) space with respect to n), and use it as a hashmap...
From mathematical perspective, the space complexity of such solution increases linearly as the length of the array grows, no matter what space unit it is - 1 bit or 8 byte.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.