Simple 330ms Java solution using one Hashtable beating 70%


  • 0
    import java.util.*;
    public class TwoSum {
    Hashtable<Integer,Integer> nums = new Hashtable<>();
    // Add the number to an internal data structure.
    public void add(int number) {
        if(nums.containsKey(number)==false){
            nums.put(number,1);
        }
        else
        {
            if(nums.get(number)==1){
                nums.put(number,2);
            }
        }
    }
    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        if(nums.size()<=1&&nums.contains(2)==false){
            return false;
        }
        Iterator<Integer> iter = nums.keySet().iterator();
        while(iter.hasNext()){
            int curr = iter.next();
            if(nums.containsKey(value-curr)==false){
                continue;
            }
            else{
                if(value-curr==curr){
                    if(nums.get(curr)!=2){
                        continue;
                    }
                }
                return true;
            }
        }
        return false;
    }
    }
    

    The main idea is to use a hash table to memorize added numbers. For find function, traverse the hash table and see if (target value - current number in the table) exists in the hash table. Take care of the condition that value - a = a. That is why how many times a number has been added need to be counted and stored.


Log in to reply
 

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