The question do not assume NO overflow, and solution do not handle


  • 0
    D
    public class TwoSum {
        Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    
    	public void add(int number) {
    	    if(!map.containsKey(number)){
    	        map.put(number,0);
    	    }
    	    map.put(number,map.get(number)+1);
    	}
    
    	public boolean find(int value) {
    	    for(int each:map.keySet()){
    	        long other = value - each;
    	        if(other>Integer.MAX_VALUE || other<Integer.MIN_VALUE){
    	               continue;
    	        }
    	        
    	        if(map.containsKey(other)){
    	            if(other == each){
    	                return map.get(other)>1;
    	            }else{
    	                return true;
    	            }
    	        }
    	    }
    	    return false;
    	}
    }
    

    this is my code which handle the overflow : by the code :

     long other = value - each;
        	        if(other>Integer.MAX_VALUE || other<Integer.MIN_VALUE){
        	               continue;
        	        }
    

    but this do not pass the online judg, got TLE.
    but when I change above code to :

    int  other = value - each;
    // if(other>Integer.MAX_VALUE || other<Integer.MIN_VALUE){
    //        	               continue;
    //        	        }
    

    it passed....

    any idea?


  • 0
    D

    test case:
    TwoSum twoSum = new TwoSum();
    twoSum.add(Integer.MIN_VALUE);
    twoSum.add(-1);

        System.out.println("result = " + twoSum.find(Integer.MAX_VALUE));
    

    result:
    result = true

    so , i think we need to consider overflow


  • 0

    Good point, thinking about overflow. Your

    long other = value - each;
    if(other>Integer.MAX_VALUE || other<Integer.MIN_VALUE){
    

    doesn't help, though. If there's any overflow, it happens during the subtraction, and you then store the already wrong result in other. And since the result of the subtraction is an int, it can never be outside of MIN/MAX and thus your if... never applies.


Log in to reply
 

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