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
  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 sums.如果重复添加某一个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.

把”最优”的code放下面.

 

NOTE:

  • 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>();
 }
}

 

Advertisements
«

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: