My Beats 99.49% Java Submission


  • 6
    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.
    public void add(int number) {
        list.add(number);
        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;
    }
    

    }


  • 0
    B

    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.


  • 0
    Y

    @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.
    	public void add(int number) {
    	    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;
    	    
    	}
    }

  • 0
    H

    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


  • 0
    Z

    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()


  • 0
    H

    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?


Log in to reply
 

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