My improved two pointer search with TreeMap, not TLE for the newest test cases


  • 3
    J
    public class TwoSum {
        TreeMap<Integer, Integer> map = new TreeMap<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) {
    	    if(map.isEmpty()){
    	        return false;
    	    }
    	    int left = map.firstKey();
    	    int right = map.lastKey();
    	    while(left<=right){
    	        if(left==right){
    	            return map.get(left)>1&&left+right==value;
    	        }
    	        int sum  = left+right;
    	        if(sum==value){
    	            return true;
    	        }
    	        else if(sum>value){
    	            if((left<<1)>value){
    	                return false;
    	            }
    	            right = map.floorKey(value-left);
    	        }
    	        else{
    	            if((right<<1)<value){
    	                return false;
    	            }
    	            left = map.ceilingKey(value-right);
    	        }
    	    }
    	    return false;
    	}
    }
    
    
    // Your TwoSum object will be instantiated and called as such:
    // TwoSum twoSum = new TwoSum();
    // twoSum.add(number);
    // twoSum.find(value);

  • 0
    F

    Thanks for the AC solution.
    Just a question, why the O(1) containsKey() in hashmap will get TLE?


  • 0
    S

    Hash solution doesn't always get TLE, you just have to optimize it (e.g. you can terminate the loop earlier if you already find a pair of numbers which give the correct sum).


Log in to reply
 

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