Two Sum III – Data structure design

Leave a comment

November 20, 2016 by oneOokay

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


初阶的想法: 储存所有的被add的numbers. 那么存nums的结构就是ArrayList.

  • nums要存有序还是无序呢?
  • 一个额外的Set来存Sums吗?
  • trade off的考虑: quick add OR quick find 以及Add多find少的情况VS find多add少的情况.
  1. number如果有序存的话:  要么Collections.sort; (O(NlogN). 要么在ArrayList里正确的index插入number (Binary Search find index + shift array: LogN + N).
  2. 不预先存sums的话,find可以用TWO SumI中的HashMap来做.这样每次都要重新构建hashmap.费时费空间. 空间为O(N*N)
  3. 先预存sums的话,在add的同时,更新sums set. O(N)


考虑到two sum.如果重复添加某一个number的话,次数多余2的number都没有意义了.

所以加入一个count 的hashmap来记录每一个number出现了多少次.出现超过两次就不需要再加入了.从而减少了nums的总数. O(1)

NOTE: 这里我commit 了代码runtime beat > 90%. 也就是ArrayList + HashMap. 在Find的时候用了Collections.sort() + two pointers 来iterate arrays. (很奇妙的是在下面的最优的算法里面run time 反而比这个慢很多. 因为HashMap的iteration要慢于ArrayList, 用hashmap 才>10%-20%左右)


TWO Sum里面有用到hashmap,这里既然已经存在一个hashmap存所有被加入的数字了,那么就可以直接用这个hashmap来查找是否存在value – key的key来判断find.

但是要注意如果key == value – key的话那么map.get(value-key)必须为2才能返回true.



  • 一个arraylist存所有的数字,一个sorted boolean
  • 每加入一个num,设sorted = false
  • find的时候,如果sorted==true,直接two pointers.如果sorted == false,那么重新sort arraylist, 把sorted设为true.
  • 这个beat > 96%的速度了…


  • HashMap的loop:map.keySet():  for (T k : map.keySet())
  • HashSet 的 Iterator:  Iterator<T> it = set.iterator()
public class TwoSum {
 // Add the number to an internal data structure.
 HashMap<Integer, Integer> map;
 public void add(int number) {
 if (!map.containsKey(number)){
 map.put(number, 1);
 }else {
 if (map.get(number) == 1){
 map.put(number, 2);
 } } }

 // Find if there exists any pair of numbers which sum is equal to the value.
 public boolean find(int value) {
 for (int key : map.keySet()){
 int res = value - key;
 if ((res == key && map.get(key) == 2) || (res != key && map.containsKey(res))){
 return true;
 } }
 return false;
 public TwoSum(){
 map = new HashMap<Integer, Integer>();



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: