LinkedHashMap + Trimming beats 99%


  • 0

    This implementation prefers add() with O(1) over find() with O(n). Besides, the code use 1) LinkedHashMap to boost the map iteration speed and 2) maxBound/minBound for trimming.

    class TwoSum {
    
        private Map<Integer, Boolean> data = null;
        private long maxBound, minBound;
        
        /** Initialize your data structure here. */
        public TwoSum() {
            data = new LinkedHashMap<>();
            maxBound = Integer.MIN_VALUE << 1;
            minBound = Integer.MAX_VALUE << 1;
        }
        
        /** Add the number to an internal data structure.. */
        public void add(int number) {
            if (data.containsKey(number)) data.put(number, true);
            else data.put(number, false);
            
            maxBound = Math.max(maxBound, number << 1);
            minBound = Math.min(minBound, number << 1);
        }
        
        /** Find if there exists any pair of numbers which sum is equal to the value. */
        public boolean find(int value) {
            if(value < minBound || value > maxBound) return false;
            
            for(int num1 : data.keySet()) {
                int num2 = value - num1;
                if (num1 == num2 && data.get(num1)) return true;
                else if (num1 != num2 && data.containsKey(num2)) return true;
            }
            
            return false;
        }
    }
    

Log in to reply
 

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