Saturday, January 17, 2015

Two Sum III Data Structure design

Two Sum III - Data structure design

 Total Accepted: 311 Total Submissions: 1345
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

I use a list, I see other implementations that use a map. But my implementation is faster. O(1) add, and O(n) find.


import java.util.*;
public class TwoSum {
 private List list;
 public TwoSum() {
  list = new ArrayList ();
 }
 public void add(int num) {
  list.add(num);
 }
 public boolean find (int sum) {
  for (int i = 0; i < list.size(); i++) {
   if (list.contains(sum - list.get(i))) {
    if (list.indexOf(sum - list.get(i)) == i)
     continue;
    return true;
   }
  }
  return false;
 }
}

No comments:

Post a Comment