Simple Java O(N) time and just a map for storage


  • 0
    N
    public class TwoSum {
    
    //this map stores the incoming integer as key and the number of 
    //its occurances as the value
    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, 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) {
        int diff = -1;
        boolean flag = false;
        boolean cond = false;
        //loop over all the keys
        for(Integer num : map.keySet()){
            //difference between number and the requested value
            diff = value-num;
            //if the above difference is equal to the current num, then update flag as true
            flag = (diff==num);
            //if the diff between the current num and requested value == current num, then
            //the map should contain more than one occurence of the current number
            cond = (map.containsKey(diff) && flag && map.get(diff) > 1);
            //if the diff between the current num and requested value != current num, then
            //we just need to check whether the map contains the value
            cond = cond || (map.containsKey(diff) && !flag);
            if(cond) return true;
        }
        return false;
    }
    

    }

    // Your TwoSum object will be instantiated and called as such:
    // TwoSum twoSum = new TwoSum();
    // twoSum.add(number);
    // twoSum.find(value);


  • 0
    Y

    Your code will get TLE.
    Are you sure it works?


  • 0
    N

    It passed all of the test cases. Does it throw a TLE for you ?


  • 0
    Y

    Yes! How does it happen?


  • 0
    N

    looks like some new test case was added, just tried to resubmit again and got a TLE
    https://www.dropbox.com/s/u8aei0gddp2u5pu/Screenshot 2015-10-25 12.01.24.png?dl=0


  • 0
    Y

    OJ often add new test case and have some strict run time limit lol


  • 0
    N

    looks like it, lol! it will be great if we can get some kind of notification when a new test case is added. Anyways thanks for letting me know :)


  • 0
    Y

    NP buddy lol!


  • 0
    R

    After the new test cases have been added, using TreeMap instead of HashMap will pass the OJ.


Log in to reply
 

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