# My Beats 99.49% Java Submission

• ``````public class TwoSum {
List<Integer> list = new ArrayList<Integer>();
Map<Integer, Integer> map = new HashMap<Integer, Integer>();

// Add the number to an internal data structure.
if (map.containsKey(number))
map.put(number, map.get(number)+1);
else
map.put(number, 1);
}

// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
for (int i = 0; i < list.size(); i++) {
int num1 = list.get(i);
int num2 = value - num1;
if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2)))
return true;
}
return false;
}
``````

}

• Good solution. You can further reduce the space complexity by not using the List<Integer> list and use the keyset of Map to iterate over the added integers.

• @buddha, so I save the space of list and iterate the keySet. However, it takes 4x time to pass the test cases and only beats ~25% of submissions.

I think the time complexity of map.keySet() is O(1), why does it take such long time?
Thanks!

``````public class TwoSum {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
// Add the number to an internal data structure.
if(!map.containsKey(number)) {
map.put(number, 1);
} else {
map.put(number, map.get(number)+1);
}
}

// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
for(int key: map.keySet()) {
int num1 = key;
int num2 = value-num1;
if( ((num1==num2)&&(map.get(num1)>1)) || ((num1!=num2)&&(map.containsKey(num2))) ) {
return true;
}
}

return false;

}
}``````

• I encountered this problem too. But it seems everyone believes getting the keyset is o(1) complexity: http://stackoverflow.com/questions/1850802/what-is-the-time-complexity-of-java-util-hashmap-class-keyset-method

• I guess the best answer comes from source code. KeySet() is doing something more than entrySet() does. check this out:
http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashMap.java#HashMap.entrySet()

• Thanks for answering...well, actually when entrySet is calling entrySet0 there seems to be something more too. How did you make sure keySet takes more time?

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