Used HashMap / T : O(1) => add, O(N) => find, S: O(N)


  • 0
    J
    public class TwoSum {
    
        HashMap<Integer, Integer> map;
        
        /** Initialize your data structure here. */
        public TwoSum() {
            map = new HashMap<Integer, Integer>();
        }
        
        /** Add the number to an internal data structure.. */ // T : O(1)
        public void add(int number) {
            if(map.containsKey(number))
                map.put(number, 2);
            else
                map.put(number, 1);
        }
        
        /** Find if there exists any pair of numbers which sum is equal to the value. */ // T : O(N)
        public boolean find(int value) {
            for(int num1 : map.keySet()){
                int num2 = value - num1;
                if(map.containsKey(num2)){
                    if(num2 != num1 || map.get(num2) == 2){
                        return true;    
                    }
                }
            }
            return false;
        }
    }
    
    /**
     * Your TwoSum object will be instantiated and called as such:
     * TwoSum obj = new TwoSum();
     * obj.add(number);
     * boolean param_2 = obj.find(value);
     */
    

Log in to reply
 

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