Question

Formatted question description: https://leetcode.ca/all/170.html

 Design and implement a TwoSum class. It should support the following operations: add and find.

     add - Add the number to an internal data structure.
     find - Find if there exists any pair of numbers which sum is equal to the value.

 For example,
 add(1); add(3); add(5);
 find(4) -> true
 find(7) -> false

Algorithm

HashMap to hold remainder.

Establish a mapping between each number and the number of occurrences, and then traverse the HashMap. For each value, first find the difference t between this value and the target value, and then you need to look at it in two cases.

• If the current value is not equal to the difference t, then return True as long as there is a difference t in the HashMap, or when the difference t is equal to the current value,
• If the number of mapping times of the HashMap is greater than 1, it means that there is another number in the HashMap that is equal to the current value, and the addition of the two is the target value

Code

Java

    // time: O(N)
    // space: O(N)
    public class TwoSum {

        // number to frequency
        private HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

        public void add(int number) {
            if (hm.containsKey(number)) {
                hm.put(number, hm.get(number) + 1);
            } else {
                hm.put(number, 1);
            }
        }

        public boolean find(int value) {
            for (Integer oneNumber : hm.keySet()) {
                int target = value - oneNumber;
                if (hm.containsKey(target)) {
                    // @note: for case: add=3, add=3, target=6
                    if (oneNumber == target && hm.get(target) < 2) {
                        continue;
                    }
                    return true;
                }
            }
            return false;
        }
    }

All Problems

All Solutions