[LeetCode] 170. Two Sum III

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.

Example 1:

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

Example 2:

add(3); add(1); add(2);
find(3) -> true
find(6) -> false

两数之和 III - 数据结构设计。Two Sum的变种，是一道设计题。实现两个函数add()和find()。

思路是用hashmap存，遍历input的时候可以找target - num1是否存在于hashmap，需要记得判断当num1 + num2 === sum时，若num1 === num2，看hashmap里面num的value是否大于1。

Java实现

 1 class TwoSum {
 2     private HashMap<Integer, Integer> map;
 3     private List<Integer> list;
 4     /** Initialize your data structure here. */
 5     public TwoSum() {
 6         map = new HashMap<>();
 7         list = new ArrayList<>();
 8     }
 9 
10     /** Add the number to an internal data structure.. */
11     public void add(int number) {
12         if (!map.containsKey(number)) {
13             map.put(number, 1);
14             list.add(number);
15         } else {
16             map.put(number, map.get(number) + 1);
17         }
18     }
19 
20     /** Find if there exists any pair of numbers which sum is equal to the value. */
21     public boolean find(int value) {
22         for (int num1 : list) {
23             int num2 = value - num1;
24             if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2))) {
25                 return true;
26             }
27         }
28         return false;
29     }
30 }
31 
32 /**
33  * Your TwoSum object will be instantiated and called as such:
34  * TwoSum obj = new TwoSum();
35  * obj.add(number);
36  * boolean param_2 = obj.find(value);
37  */

JavaScript实现

 1 /**
 2  * Initialize your data structure here.
 3  */
 4 var TwoSum = function() {
 5     this.map = {};
 6 };
 7 
 8 /**
 9  * Add the number to an internal data structure..
10  * @param {number} number
11  * @return {void}
12  */
13 TwoSum.prototype.add = function(number) {
14     if (this.map[number]) {
15         this.map[number]++;
16     } else {
17         this.map[number] = 1;
18     }
19 };
20 
21 /**
22  * Find if there exists any pair of numbers which sum is equal to the value.
23  * @param {number} value
24  * @return {boolean}
25  */
26 TwoSum.prototype.find = function(value) {
27     for (var key in this.map) {
28         var num1 = key;
29         var num2 = value - key;
30         if (this.map[num2]) {
31             if (num1 != num2 || this.map[num2] > 1) {
32                 return true;
33             }
34         }
35     }
36     return false;
37 };
38 
39 /**
40  * Your TwoSum object will be instantiated and called as such:
41  * var obj = new TwoSum()
42  * obj.add(number)
43  * var param_2 = obj.find(value)
44  */

LeetCode 题目总结