170. Two Sum III - Data structure design

time: find - O(n), add: O(1)

space: O(n)

class TwoSum {
    private Map<Integer, Integer> map;
    public TwoSum() {
        map = new HashMap<>();
    }
    
    public void add(int number) {
        map.put(number, map.getOrDefault(number, 0) + 1);
    }
    
    public boolean find(int value) {
        for (Integer num1 : map.keySet()) {
            int num2 = value - num1;
            
            int num2Count = (num1 == num2) ? 2 : 1;
            if (map.getOrDefault(num2, 0) >= num2Count) {
                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);
 */

Last updated

Was this helpful?