题目：

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) -> truefind(7) -> false

链接： 

题解：

设计two sum，这道题用hashmap很适合，加入是O(1)，查找的话要遍历整个keyset，所以是O(n)。

Time Complexity - O(n) , Space Complexity - O(n)

public class TwoSum {    Map
     
       map = new HashMap<>();    public void add(int number) {        if(map.containsKey(number))            map.put(number, map.get(number) + 1);        else            map.put(number, 1);    }    public boolean find(int value) {        for(int i : map.keySet()) {            int res = value - i;            if(map.containsKey(res)) {                if(res == i && map.get(i) >= 2 )                    return true;                if(res != i)                    return true;            }        }                return false;    }}
     

 

二刷:

使用了与一刷一样的方法，这样看起来比较慢，要改进。 

好好研究了一下discuss，发现了几个问题

1. 遍历整个map的时候，用entrySet比keySet快
2. 可以建一个set保存之前查询过并且找到答案的value
3. 使用ArrayList来保存之前加入过的数字，再遍历这个ArrayList比遍历HashMap的keySet和entrySet都要快很多...

Java:

Time Complexity - O(n) , Space Complexity - O(n)

public class TwoSum {    Map
     
       map = new HashMap<>();    Set
      
        valueSet;    public TwoSum() {        map = new HashMap<>();        valueSet = new HashSet<>();    }        // Add the number to an internal data structure.    public void add(int number) {        if (!map.containsKey(number)) {            map.put(number, 1);            } else {            map.put(number, 2);        }    }    // Find if there exists any pair of numbers which sum is equal to the value.    public boolean find(int value) {        if (valueSet.contains(value)) {            return true;        }        for (int i : map.keySet()) {            int remain = value - i;            if (map.containsKey(remain)) {                if ((remain == i && map.get(remain) > 1) || remain != i) {                    valueSet.add(value);                    return true;                    }             }        }        return false;    }}// Your TwoSum object will be instantiated and called as such:// TwoSum twoSum = new TwoSum();// twoSum.add(number);// twoSum.find(value);
      
     

 

Reference:

https://leetcode.com/discuss/76823/beats-100%25-java-code