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 Listlist; 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