首页 > 代码库 > [LintCode] Two Sum - Data Structure Design
[LintCode] Two Sum - Data Structure Design
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.
Example
add(1); add(3); add(5);
find(4) // return true
find(7) // return false
For two sum, typically we have two solutions to select from: using hash table or sorting then
using two pointers technique.
Using hash table gives us a O(n) runtime and O(n) space algorithm;
Using sorting/two pointers technique gives us a O(n*logn) time, and O(1) space(if quick sort is used) algorithm.
This problem is different with the Two Sum problem in the following two aspects.
1. We need to design a data structure that supports adding new element to the internal
data structure that stores all elements.
2. We only check if such a pair exists or not; no need to return the indices as is
required in the Two Sum problem.
Since we need to maintain such an internal data structure that stores all elements and
an add element operation, we need to use O(n) space for this regardless which approach
we use. So this makes the hash table solution better as it has a better runtime of O(n).
Solution. O(n) time, O(n) space, Hash table
Since we only check if such a pair exists, a hash set and one pass is sufficient.
Another implementation is to iterate through the list and store all key-value pairs(value - nums[i], nums[i])
in a hash map. Then during the second pass, for each element nums[i], check if a key of
value - nums[i] exists. This still gives us O(n) runtime but obviously not as good
as the one pass solution. However, this two passes solution is useful when we need
to return indices as is required in Two Sum.
1 public class TwoSum { 2 private ArrayList<Integer> numbers; 3 4 public TwoSum() 5 { 6 this.numbers = new ArrayList<Integer>(); 7 } 8 9 // Add the number to an internal data structure. 10 public void add(int number) { 11 this.numbers.add(number); 12 } 13 14 // Find if there exists any pair of numbers which sum is equal to the value. 15 public boolean find(int value) { 16 HashSet<Integer> set = new HashSet<Integer>(); 17 for(int i = 0; i < this.numbers.size(); i++) 18 { 19 if(set.contains(numbers.get(i))) 20 { 21 return true; 22 } 23 set.add(value - numbers.get(i)); 24 } 25 return false; 26 } 27 } 28 // Your TwoSum object will be instantiated and called as such: 29 // TwoSum twoSum = new TwoSum(); 30 // twoSum.add(number); 31 // twoSum.find(value);
Related Problems
Two Sum - Input array is sorted
Word Abbreviation Set
Two Sum - Difference equals to target
Two Sum - Less than or equal to target
Two Sum - Unique pairs
Two Sum - Closest to target
Two Sum - Greater than target
Two Sum
[LintCode] Two Sum - Data Structure Design
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。