170. TwoSum III

Leetcode HashMap Design

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

分析

/**
 * 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
 *
 *
 * 需要注意数据有可能重复的情况
 *
 */
public class Q170TwoSumIII {
    // map stores key: num, value: count
    private Map<Integer, Integer> map = new HashMap<>();

    public void add(int num) {
        if (map.containsKey(num)) {
            map.put(num, map.get(num) + 1); // count ++
        } else {
            map.put(num, 1);
        }
    }

    public boolean find(int target) {
        for (Integer num: map.keySet()) {
            if ((target != num * 2) && map.containsKey(target-num)) {
                return true;
            } else if ((target == num * 2) && (map.get(num) > 1)) {
                return true;
            } // end if
        } // end for
        return false;
    } // end find
}