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 }
近期评论